Remove Duplicates from Sorted List — Solution

Problem

Given a sorted linked list, remove all duplicate nodes so that each value appears exactly once and return the deduplicated list.

[1,1,2,2,3]

• Input: head = [1, 1, 2, 2, 3]
• Output: [1, 2, 3]
• Explanation: Both 1 and 2 appeared twice; after removing duplicates each value appears exactly once.

Intuition

Because the list is already sorted, any duplicate values must be adjacent to each other — you never need to look backward or use extra memory to track what you've seen. A single pointer scan comparing each node to its immediate successor is enough: whenever two neighbors share a value, wire around the second one.

Solution — Single Pass

Walk the list with one pointer. When the current node has the same value as the next, bypass the next node by rewiring current.next to skip it. Only advance the pointer when the values differ — this ensures we collapse runs of any length.

1. Start current at the head.
2. Loop while current and current.next both exist.
3. If current.val == current.next.val, set current.next = current.next.next to skip the duplicate.
4. Otherwise, advance current = current.next.
5. Return the original head (unchanged; we modified links in place).

1def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
2    current = head
3    while current and current.next:
4        if current.val == current.next.val:
5            current.next = current.next.next  # skip the adjacent duplicate
6        else:
7            current = current.next  # only advance when values differ
8    return head

Time: O(n) — each node is visited at most once in the single pass.

Space: O(1) — only one pointer variable; nodes are modified in place with no extra data structures.

Complexity Summary

Common Mistakes

• Advancing current after every iteration regardless of a match — when you skip a duplicate, you must not advance; the next node after the rewire may itself be another duplicate with the same value, and advancing would miss it (e.g., 1 → 1 → 1 would leave one duplicate behind).
• Checking current.val == current.val — accidentally comparing the current node to itself (a copy-paste slip) rather than to current.next.val; this condition is always true and produces an infinite loop.
• Forgetting to guard current.next != null — dereferencing current.next.val without first confirming current.next exists raises a null pointer error on the tail node.
• Trying to use a hash set — this works but wastes O(n) space and misses the key insight that sorting already eliminates the need for membership tracking.
• Returning current instead of head — current ends up at the tail after the loop; the caller needs the original head pointer, which is unchanged and must be returned instead.

Related Problems

• remove-duplicates-from-sorted-list-ii — harder variant that removes all nodes whose value appears more than once, requiring a predecessor pointer
• merge-two-sorted-lists — same pointer-rewiring mechanics on a sorted linked list
• palindrome-linked-list — traverses a linked list comparing node values, similar iteration pattern
• odd-even-linked-list — rearranges a linked list in place using the same style of next pointer reassignment
• reverse-linked-list — foundational linked list pointer manipulation that underpins all list-rewriting problems