LeetCode 83 – Remove Duplicates from Sorted List

Remove Duplicates from Sorted List is a five-line problem with one bug in it, and essentially everyone writes that bug the first time. It is also the cleanest place to learn when a linked-list problem needs a dummy head and when it does not — a question that decides the shape of most linked-list answers before any logic is written.

The problem

Given the head of a sorted linked list, delete all duplicates so that each value appears only once. Return the list, still sorted.

1 -> 1 -> 2                ->  1 -> 2
1 -> 1 -> 2 -> 3 -> 3      ->  1 -> 2 -> 3
1 -> 1 -> 1                ->  1            three in a row
[]                          ->  []
1 -> 2 -> 3                ->  1 -> 2 -> 3  nothing to do

Sorted is what makes this easy: equal values are necessarily adjacent, so a duplicate is always the node immediately after. On an unsorted list you would need a hash set and the problem would be a different one.

The bug: advancing after a deletion

The natural loop is "look at the next node; if it matches, unlink it; move on". The bug is in "move on":

1 -> 1 -> 1 -> 2      current at the first node

unlink the second:
1 -> 1 -> 2           current still at the first node

WRONG: advance anyway
1 -> 1 -> 2           current now at the second 1 -- and the duplicate survives
     ^

After a deletion, current has a new next node that has not been examined yet. Advancing skips it. The rule is: advance only when you did not delete. Three identical values in a row is the smallest input that exposes it, and two-in-a-row test cases pass happily without it.

No dummy head — and that is worth saying

The reflex on linked-list problems is to allocate a dummy node pointing at the head, so that deleting the first element needs no special case. Here it is unnecessary, and knowing why is the transferable part:

A dummy head is needed exactly when the head itself might be removed or replaced.

This problem keeps one of each value, and the first node is always the first occurrence of its value, so it always survives. The head never changes, so return head is correct and no dummy is required.

Contrast Remove Duplicates from Sorted List II (82), which deletes every copy of any duplicated value. There 1 -> 1 -> 2 returns 2, the head does change, and a dummy becomes mandatory. Naming that difference unprompted is a strong signal.

Java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;

        while (current != null && current.next != null) {
            if (current.next.val == current.val) {
                current.next = current.next.next;   // unlink; do NOT advance
            } else {
                current = current.next;
            }
        }

        return head;                                 // the head always survives
    }
}

current != null handles the empty list and current.next != null handles the last node. Both are needed, in that order — Java's && short-circuits, so the second dereference is only reached when the first is true. Writing them the other way round throws on an empty list.

Nothing is freed explicitly. In Java the unlinked node becomes unreachable and the collector deals with it; in a language with manual memory management this is where you would free it, and the detail is worth a sentence if the interviewer works in C++.

Python

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        current = head

        while current and current.next:
            if current.next.val == current.val:
                current.next = current.next.next     # unlink; do NOT advance
            else:
                current = current.next

        return head

while current and current.next reads exactly as the invariant: there is a node, and it has a successor to compare against.

Complexity

	Time	Space
Single pass	`O(n)`	`O(1)`

Each node is visited once — either it is deleted, or current moves past it, and neither happens twice to the same node. The while loop looks like it could revisit, but every iteration removes a node or advances, so the total is bounded by n.

The pointer surgery is done in place, so the extra space is the single current reference.

A recursive version, for contrast

    def deleteDuplicatesRecursive(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        head.next = self.deleteDuplicatesRecursive(head.next)
        return head.next if head.val == head.next.val else head

Elegant, and worth being able to write. It is also O(n) stack, which on a list of a hundred thousand nodes overflows — the same trade Number of Islands makes between DFS recursion and an explicit queue. The iterative version is the one to give unless recursion was asked for.

The pattern

"Compare against the next node and unlink" recurs throughout linked lists: Remove Linked List Elements (203) removes by value and does need a dummy, because the head can match. Remove Nth Node From End (19) needs one for the same reason. Remove Duplicates from Sorted Array (26) is this on an array, where the same idea becomes a read pointer and a write pointer.

Sorting first is what makes every one of them a single pass. If you find yourself wanting a hash set on a sorted structure, check whether adjacency has already given you what you need.

What the interviewer is checking

That you do not advance after a deletion — test with three equal values in a row.
That you can say why no dummy head is needed, and when one would be.
The empty list and the single-node list.
The null checks in the right order, so an empty list does not throw.
That sortedness is what makes duplicates adjacent, and what would change without it.
A list with no duplicates at all, returned unchanged.