Remove Duplicates from Sorted Linked List

Remove Duplicates from Sorted Linked List is the cleanest introduction to in-place linked-list surgery. The list is already sorted, which hands you a gift: any duplicate of a value sits directly next to it. So you never need to search — you only ever compare a node with the one right after it.

The slow way first

You could collect every value into a set, then rebuild a brand-new list from the distinct values. That works, but it wastes O(n) extra memory and ignores the structure you were handed. Because the list is sorted, equal values are guaranteed to be adjacent — there is no reason to remember anything. You can fix the list in place with a single pointer and O(1) extra space.

The question to ask: while I am standing on one node, what is the only thing that can be a duplicate of it? The answer is the very next node. That is the whole problem.

The idea: one pointer, compare with the neighbor

Keep a pointer cur on the last node you have decided to keep. Look at cur.next:

• If cur.next.val == cur.val, the next node is a duplicate. Splice it out by setting cur.next = cur.next.next. Do not move cur — the new neighbor might also be a duplicate.
• If they differ, this neighbor is a new value to keep, so advance: cur = cur.next.

Repeat while cur and cur.next both exist.

The reason cur stays put after a splice is subtle but important: a run of three or more equal values (like 3 -> 3 -> 3) needs cur to keep eating neighbors until the value finally changes.

Walk through it

Step through the animation. cur starts on the first 1. Its neighbor is another 1, so that node and its edge fade out and cur.next jumps to the 2. Now the neighbor differs, so cur advances to the 2, then to the first 3. There it meets the second 3 — another duplicate — which gets spliced out, leaving cur.next as None. The loop ends and we return the head: 1 -> 2 -> 3.

Pseudocode

cur = head
while cur is not None and cur.next is not None:
    if cur.next.value == cur.value:
        cur.next = cur.next.next     # drop the duplicate, do NOT move cur
    else:
        cur = cur.next               # new value, step forward
return head

The Python solution

def delete_duplicates(head):
    cur = head
    while cur and cur.next:
        if cur.next.val == cur.val:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return head

• cur = head puts the pointer on the first node, which we always keep.
• while cur and cur.next stops cleanly at the tail (and handles the empty list — cur is None).
• Line 4 is the comparison — the only check we ever make, between a node and its immediate neighbor.
• Line 5 is the splice: cur.next = cur.next.next unlinks the duplicate so it is no longer reachable.
• The else branch is the only place cur moves. After a splice we loop again from the same cur to catch longer runs.

Complexity

Every node is visited once, so the time is O(n). We rewire a few next pointers and store nothing extra, so the space is O(1) — the in-place win the sorted order makes possible.

When this pattern shows up

Practice