82. Remove Duplicates from Sorted List II

二刷 06/2022

Version #1 Not Optimal 

站在一个点上同时向前看和向后看，如果都没有相等的value证明不是一个duplicate点，就接到答案上

看了之前的答案感觉这个写法不是最优的

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 79.44% of Java online submissions for Remove Duplicates from Sorted List II.

Memory Usage: 43.8 MB, less than 38.44% of Java online submissions for Remove Duplicates from Sorted List II.

class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        ListNode dummy = new ListNode(0);

        ListNode curr = dummy;

        ListNode prev = null;

        while (head != null) {

            if ((prev == null || prev.val != head.val) && (head.next == null || head.next.val != head.val)) {

                curr.next = head;

                curr = curr.next;

            }

            prev = head;

            head = head.next;

            curr.next = null;

        }

        return dummy.next;

    }

}

Version #2 Better

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 79.44% of Java online submissions for Remove Duplicates from Sorted List II.

Memory Usage: 43.1 MB, less than 76.10% of Java online submissions for Remove Duplicates from Sorted List II.

class Solution {

    public ListNode deleteDuplicates(ListNode head) {

        ListNode dummy = new ListNode(0);

        dummy.next = head;

        ListNode slow = dummy;

        ListNode fast = head;

        while (fast != null) {

            while (fast.next != null && fast.val == fast.next.val) {

                fast = fast.next; // reach the last duplicate node

            }

            // The fast has skipped duplicates

            if (slow.next != fast) {

                slow.next = fast.next;

            } else {

                slow = slow.next;

            }

            fast = fast.next;

        }

        return dummy.next;

    }

}

一刷

有重复的就向后跳
如果跳了证明有重复 就prev.next = curr.next 此时prev不变
如果没跳prev向后移动一位
76.20 %

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        //    p        c
        // 1->2->3->3->4->4->5
        while (curr != null) {
            while (curr.next != null && curr.next.val == curr.val) {
                curr = curr.next;
            }
            if (curr != prev.next) {
                prev.next = curr.next;
            } else {
                prev = prev.next;
            }
            curr = curr.next;
        }
        return dummy.next;
    }
}