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