79. Remove Duplicates from Sorted List II

Because the list is sorted, duplicates are consecutive. Keep a pointer to the last confirmed-unique node; whenever the node ahead starts a run of equal values, skip the entire run so no copy remains. A dummy head handles deletions at the front.

Idea

Unlike the version that keeps one copy, here every node of a duplicated value must go. Since the list is sorted, equal values are adjacent, so we can detect a duplicate run by comparing cur.val with cur.next.val. A prev pointer tracks the last node guaranteed to be unique; when a run is found, we advance past the whole run and link prev directly to whatever follows.

A dummy node before the head lets us delete leading duplicates uniformly.

Algorithm

1. dummy -> head; prev = dummy, cur = head.
2. While cur:
   • If cur.next exists and cur.val == cur.next.val: remember the value, advance cur past all nodes with that value, then set prev.next = cur (splicing out the run).
   • Else: prev = cur, cur = cur.next.
3. Return dummy.next.

Worked example: 1→2→3→3→4→4→5

• 3 starts a run (3,3) → skip both; 4 starts a run (4,4) → skip both.

Result: 1→2→5.

Complexity

• Time: O(n).
• Space: O(1).

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode cur = head;
        while (cur != null) {
            if (cur.next != null && cur.val == cur.next.val) {
                int val = cur.val;
                while (cur != null && cur.val == val) {
                    cur = cur.next;
                }
                prev.next = cur;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}