Remove Duplicates from Sorted List

When a problem says “remove duplicates,” the first instinct is often to reach for a set. That works for an unsorted list, but it misses the key clue here: the linked list is already sorted.

A sorted list puts equal values next to one another. That turns duplicate detection into a local comparison, and the complete Remove Duplicates from Sorted List solution needs only one traversal pointer.

The critical rule is simple:

When you bypass a duplicate, keep the current pointer where it is. Advance only after the next node has a different value.

The contract: keep one node per value

The input is the head of a singly linked list sorted in ascending order. The result must keep exactly one node for every value.

For example:

1 → 1 → 2 → 3 → 3

becomes:

1 → 2 → 3

The first node in each repeated run stays. Later nodes with the same value are removed by changing links.

This is different from Remove Duplicates from Sorted List II, where every value that appears more than once is removed. Under this problem's contract:

2 → 2 → 2

becomes:

2

not an empty list.

The head does not need special treatment. If the list is nonempty, the first node belongs to the first value run and is retained. An empty list simply returns None.

Recognize the sorted-run signal

Without sorted order, duplicate detection is global. You may need to remember every value already seen:

seen = set()

That baseline takes linear extra space. It is valid as a first thought, but it ignores the strongest property of the input.

In a sorted list, equal values must be adjacent. A value cannot disappear and then reappear later:

1 → 1 → 2 → 2 → 3 → 3

contains contiguous runs. Once the pointer moves past the run of 1s, no later node can contain 1.

That gives us three concrete obligations:

1. Keep the first node in each value run.
2. Bypass later nodes with the same value.
3. Keep the untouched suffix reachable after every link change.

This is a one-pointer traversal problem. Fast and slow pointers would add machinery for a problem that has no cycle, midpoint, or distance requirement. The list's order already gives us the structure we need.

Derive the pointer deletion

Use a pointer named current.

At every step, current represents the retained node at the end of the cleaned portion of the list. Compare its value with the value of current.next.

There are only two cases.

The next value matches

Suppose the list currently looks like this:

current
   ↓
   1 → 1 → 1 → 2

The first 1 is the representative we keep. To remove the next 1, bypass it:

current.next = current.next.next

After that assignment:

current
   ↓
   1 ───────→ 1 → 2

The second 1 shown after the arrow is the next node that still needs checking. Since it may also be a duplicate, current must stay where it is.

Repeat the same operation:

current
   ↓
   1 ─────────────→ 2

Now the next value is different.

The next value differs

If current.val and current.next.val are different, the current run is complete. Move forward:

current = current.next

The new node becomes the retained representative for the next value run.

A dummy node is unnecessary here. The algorithm never removes the head; it only removes nodes after a retained node. That lets the original head remain the answer throughout the traversal.

The invariant that keeps the mutation safe

Pointer code becomes easier to trust when each variable has a precise job.

Use this loop invariant:

Before each iteration, every node from head through current is deduplicated, remains reachable from head, and current is the retained last node of that processed prefix.

Now check both branches against the invariant.

If the next node has the same value, we execute:

current.next = current.next.next

This removes one duplicate from the reachable chain. The retained prefix does not change, and the suffix after the removed node is still connected through current.next. The invariant remains true.

If the next node has a different value, we advance current. Because the list is sorted, no later node can match the value of the completed run. The prefix remains deduplicated, so the invariant still holds.

The algorithm terminates because every iteration does one of two things:

• advances current to a later retained node, or
• bypasses a duplicate node.

It never moves backward, and it never revisits a node that has already been bypassed.

The local condition at the end is also enough for the global result. In a sorted list, if no adjacent nodes have equal values, then no value can occur twice anywhere in the list.

Python implementation

Assume the usual node definition:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

The iterative solution is:

from typing import Optional

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

        while current is not None and current.next is not None:
            if current.val == current.next.val:
                # Remove the duplicate node.
                current.next = current.next.next
            else:
                # The current value run is complete.
                current = current.next

        return head

The loop guard checks two things:

• current is not None, so we have a node whose value can be read.
• current.next is not None, so there is a neighbor to compare and possibly remove.

The solution reuses the original nodes. It does not build a new list or copy values into another structure. The result is formed by rewiring next references.

After a bypass, the rest of the list is still reachable:

current → duplicate → suffix

becomes:

current ───────────→ suffix

That reachability property is the entire safety story behind the mutation.

Dry run: a mixed list

Consider:

1 → 1 → 2 → 3 → 3

Start with current at the first node:

current
   ↓
   1 → 1 → 2 → 3 → 3

The next value is also 1, so bypass the next node. Do not advance:

current
   ↓
   1 → 2 → 3 → 3

Now 1 and 2 differ, so advance:

       current
          ↓
   1 → 2 → 3 → 3

The next value differs again, so advance:

           current
              ↓
   1 → 2 → 3 → 3

The next value matches 3, so bypass it and keep current fixed:

           current
              ↓
   1 → 2 → 3

Now current.next is None, so the loop stops. The original head still points to the resulting list.

Edge cases and failure modes

Empty list

For:

None

current starts as None. The loop does not execute, and the method returns None.

Singleton list

For:

7

current.next is None, so there is no comparison to make. The same node is returned unchanged.

Already unique list

For:

1 → 2 → 3

Every comparison differs. The pointer advances through the list, and no links change.

All values are equal

For:

4 → 4 → 4 → 4

The pointer stays on the first 4 while each later node is bypassed:

4 → 4 → 4 → 4
4 → 4 → 4
4 → 4
4

This case exposes the most important rule in the problem.

Duplicate run at the tail

For:

1 → 2 → 3 → 3

The final duplicate is bypassed, leaving 3.next as None. The loop guard prevents the code from trying to read a value through a missing node.

The central bug: advancing after deletion

This version is wrong:

if current.val == current.next.val:
    current.next = current.next.next
    current = current.next  # Bug

On:

1 → 1 → 1

the first deletion produces:

1 → 1

But advancing immediately moves current to the second 1. The algorithm can stop with a duplicate still present.

Deletion changes the neighbor. Re-check the new neighbor before moving on.

Complexity and implementation checks

Let n be the number of nodes.

The time complexity is O(n). The pointer moves forward across retained nodes, and each duplicate is bypassed once. There is no repeated scan of an already processed section.

The auxiliary space is O(1). The algorithm stores only current; it does not allocate a set, replacement list, or additional chain.

A set-based solution can also scan in O(n) expected time, but it uses O(n) extra space. More importantly, it treats a local sorted-run problem as if it required global memory. The preferred solution uses the input's strongest structural guarantee.

“In place” means the reachable list is changed by rewiring existing next links. It does not require constructing a replacement chain. Once a duplicate is bypassed, it is no longer reachable from the returned head; questions about when the runtime reclaims that detached node are separate from the algorithm's pointer logic.

Before submitting, check:

• Do I compare current with current.next?
• Do I verify that both nodes exist before reading their values?
• After deleting a duplicate, do I keep current fixed?
• After a mismatch, do I advance current?
• Do I return the original head?

The transferable recognition rule

Sorted order turns global duplicate detection into local neighbor comparison.

That is the pattern to carry into other problems:

1. Identify the structural guarantee.
2. Convert it into a local comparison.
3. Define what the current pointer owns.
4. Mutate only the link required by the output contract.
5. After every mutation, verify that the processed prefix is clean and the untouched suffix remains reachable.

For this problem, the output contract says to retain one representative per value run. So retain the first node, bypass later equal nodes, and do not advance after deletion.

Do not memorize the code template first. Watch the pointer move. The durable interview skill is knowing which node remains responsible for the next decision after the structure changes.