Remove Duplicates from Sorted List II (LeetCode 82)

The problem

You get the head of a linked list sorted in ascending order. Remove every node whose value appears more than once, so only values that were unique in the original list survive. Return the head of the result, still sorted.

Input:  1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5
Output: 1 -> 2 -> 5

3 and 4 each appear twice, so all copies of them are removed.

How to think about it

Start with brute force. Count every value in a hash map in one pass, then build a new list of only the values with count 1. That is O(n) time but O(n) extra space, and it ignores that the list is sorted.

The key insight: in a sorted list, duplicates sit next to each other in a run. So you can tell whether a node is a duplicate just by comparing it with its neighbour. When cur.val == cur.next.val, you’ve found the start of a run. Walk cur to the last node of that run, then connect the node before the run straight to whatever comes after it. The whole run disappears in one pointer write.

prev is the last node you’ve decided to keep. It only moves forward when the current node is not part of a run. When you skip a run, prev stays put, because the node after the run might itself start another run (like 3 3 4 4 in the example).

A dummy head handles runs at the front. If the list starts 1 1 2, the real head gets deleted. With a dummy in front, prev always exists and d.next is always the correct answer.

Which pattern is this? Linked-list rewiring with a dummy head. The tell is “delete nodes, possibly including the head”.

Approach

1. Create d = ListNode(0, head); set prev = d and cur = head.
2. While cur exists:
   • if cur.next exists and has the same value, advance cur to the last node of the run, then set prev.next = cur.next (drop the whole run);
   • otherwise cur is unique, so move prev forward to it.
   • move cur one step forward.
3. Return d.next.

Solution

class ListNode:                                   # LeetCode's node type
    def __init__(self, val=0, next=None):
        self.val = val; self.next = next

def delete_dups_ii(head):
    d = ListNode(0, head); prev = d; cur = head   # prev = last node we keep
    while cur:
        if cur.next and cur.val == cur.next.val:  # start of a run of duplicates
            while cur.next and cur.val == cur.next.val: cur = cur.next   # go to end of run
            prev.next = cur.next                  # unlink the whole run; prev stays
        else:
            prev = prev.next                      # cur is unique: keep it
        cur = cur.next
    return d.next
# delete_dups_ii([1,2,3,3,4,4,5]) -> [1,2,5]

Dry run

On 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 (values shown for cur after any run skip):

Result: 1 -> 2 -> 5.

Complexity

• Time: O(n). cur moves forward on every step, inner loop included, so each node is visited once.
• Space: O(1). A dummy node and two pointers.

Edge cases and pitfalls

• All duplicates ([1,1,2,2]): every run is skipped, d.next becomes None, and the answer is an empty list.
• Run at the head ([1,1,1,2,3]): the dummy makes this work; returning the original head would be wrong.
• Run at the tail ([1,2,2]): prev.next = cur.next sets prev.next to None, which correctly ends the list.
• Moving prev after a skip. If you advance prev onto the node after the run, a second run right after it (like 4 4) would be kept by mistake.
• Confusing it with LeetCode 83, which keeps one copy of each value. Here no copy survives.

Related problems

• Remove Duplicates from Sorted Array (LeetCode 26): the array version that keeps one copy, with a read/write pointer.
• Remove Nth Node From End of List (LeetCode 19): another deletion that leans on a dummy head.
• Merge Two Sorted Lists (LeetCode 21): same dummy-head habit for lists whose head may change.