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/

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

• 1.常规解法

思路：
1.遍历该链表，如果 cur.val == cur.next.val，则删除掉重复元素
2.如果 cur.val ！= cur.next.val，则将节点向后移动一位
3.那么当到最后一个节点时，就可以删除掉重复元素了

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节点指向的元素，同时将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.假设头节点之后的节点都是没有重复的，那个我们只需判断 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

---

• 源码

• 我会随时更新新的算法，并尽可能尝试不同解法，如果发现问题请指正

• Github