LeetCode 83. 刪除排序鏈表中的重復元素

83. 刪除排序鏈表中的重復元素

給定一個排序鏈表,刪除所有重復的元素钮孵,使得每個元素只出現一次。

示例 1:

輸入: 1->1->2
輸出: 1->2

示例 2:

輸入: 1->1->2->3->3
輸出: 1->2->3

來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權,非商業(yè)轉載請注明出處权悟。


  • 1.常規(guī)解法

思路:
1.遍歷該鏈表,如果 cur.val == cur.next.val推盛,則刪除掉重復元素
2.如果 cur.val 峦阁!= cur.next.val,則將節(jié)點向后移動一位
3.那么當到最后一個節(jié)點時耘成,就可以刪除掉重復元素了

public static class ListNode {

        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        //用于測試用例
        public ListNode(int[] arr) {
            if (arr == null || arr.length == 0) throw new NullPointerException("array is Empty");
            this.val = arr[0];
            ListNode cur = this;
            for (int i = 1; i < arr.length; i++) {
                cur.next = new ListNode(arr[i]);
                cur = cur.next;
            }
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            ListNode cur = this;
            while (cur != null) {
                res.append(cur.val + "->");
                cur = cur.next;
            }
            res.append("NULL");
            return res.toString();
        }

    }

    public static ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }

復雜度分析:
時間復雜度:O(n)榔昔,假設 n 是列表的長度,那么時間復雜度為 O(n)瘪菌。
空間復雜度:O(1)

  • 2.快慢指針法

思路:
1.初始化兩個指針件豌,一個慢指針slow指向head, 而快指針fast指向head.next
2.當slow.var == fast.var 時控嗜,刪除掉當前fast節(jié)點指向的元素,同時將fast向后移
3.當slow.var != fast,var 時骡显,同時將兩個指針向后移動一位

image.png
public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null) {
           if (fast.val != slow.val) {
               fast = fast.next;
               slow = slow.next;
           } else {
               slow.next = fast.next;
               fast = fast.next;
           }
        }
        return head;
    }

復雜度分析:
時間復雜度:O(n)
空間復雜度:O(1)

  • 3.遞歸法

思路:
1.假設頭節(jié)點之后的節(jié)點都是沒有重復的疆栏,那個我們只需判斷 head.next.val 和 head.val 值是否相同
2.如果相同曾掂,返回 head.next,不同返回 head即可

public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        head.next = deleteDuplicates(head.next);
        return head.val == head.next.val ? head.next : head;
    }

復雜度分析:
時間復雜度:O(n)
空間復雜度:O(n)壁顶,由于使用了遞歸珠洗,將會使用隱式棧空間若专,遞歸深度可能會達到n層

  • 測試用例

public static void main(String[] args) {
        int[] arr = new int[] {1, 1, 2, 3, 3, 4};
        ListNode listNode = new ListNode(arr);
        System.out.println(listNode);
        System.out.println("刪除鏈表中的重復元素" + deleteDuplicates3(listNode));
    }
  • 結果

1->1->2->3->3->4->NULL
刪除鏈表中的重復元素1->2->3->3->4->NULL

  • 源碼

  • 我會隨時更新新的算法许蓖,并盡可能嘗試不同解法,如果發(fā)現問題請指正
  • Github
最后編輯于
?著作權歸作者所有,轉載或內容合作請聯系作者
  • 序言:七十年代末陪白,一起剝皮案震驚了整個濱河市迫靖,隨后出現的幾起案子邦尊,更是在濱河造成了極大的恐慌,老刑警劉巖米酬,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現場離奇詭異趋箩,居然都是意外死亡赃额,警方通過查閱死者的電腦和手機,發(fā)現死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進店門叫确,熙熙樓的掌柜王于貴愁眉苦臉地迎上來跳芳,“玉大人,你說我怎么就攤上這事竹勉》膳瑁” “怎么了?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵饶米,是天一觀的道長桨啃。 經常有香客問我,道長檬输,這世上最難降的妖魔是什么照瘾? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮丧慈,結果婚禮上析命,老公的妹妹穿的比我還像新娘。我一直安慰自己逃默,他們只是感情好鹃愤,可當我...
    茶點故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著完域,像睡著了一般软吐。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上吟税,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天凹耙,我揣著相機與錄音姿现,去河邊找鬼。 笑死肖抱,一個胖子當著我的面吹牛备典,可吹牛的內容都是我干的。 我是一名探鬼主播意述,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼提佣,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了荤崇?” 一聲冷哼從身側響起拌屏,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎天试,沒想到半個月后槐壳,有當地人在樹林里發(fā)現了一具尸體,經...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡喜每,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年务唐,在試婚紗的時候發(fā)現自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片带兜。...
    茶點故事閱讀 40,912評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡枫笛,死狀恐怖,靈堂內的尸體忽然破棺而出刚照,到底是詐尸還是另有隱情刑巧,我是刑警寧澤,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布无畔,位于F島的核電站啊楚,受9級特大地震影響,放射性物質發(fā)生泄漏浑彰。R本人自食惡果不足惜恭理,卻給世界環(huán)境...
    茶點故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望郭变。 院中可真熱鬧颜价,春花似錦、人聲如沸诉濒。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽未荒。三九已至专挪,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背狈蚤。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工困肩, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人脆侮。 一個月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像勇劣,于是被迫代替她去往敵國和親靖避。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,922評論 2 361