Remove Duplicates from Sorted List II

A duplicate run is a decision you must finish before you reconnect the list.

The key distinction is easy to miss: this problem removes every node belonging to a repeated value. It does not keep the first occurrence. The solution is to scan one complete sorted run, classify it, and only then decide whether to retain or bypass it.

The contract: delete whole duplicate runs

You receive a sorted singly linked list. The result must contain only values that appeared exactly once in the original list.

For example:

1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

becomes:

1 -> 2 -> 5

Both 3 nodes disappear. Both 4 nodes disappear.

That is the semantic trap. The neighboring “Remove Duplicates from Sorted List” problem keeps one copy of each value. Here, a repeated value contributes zero nodes to the output.

The supplied constraints are small—between 0 and 300 nodes, with node values from -100 to 100—but the intended technique is still worth deriving. The list is sorted in ascending order, so equal values form contiguous runs. We can process each run once:

1. Keep a pointer to the last node already proven safe to retain.
2. Scan to the end of the current equal-valued run.
3. Retain the run if it contains one node.
4. Bypass the entire run if it contains duplicates.

A dummy node gives every run a predecessor, including a duplicate run that begins at the original head.

Recognize the sorted-run signal

Without sortedness, deciding whether a node's value appears again is a global frequency problem. You might need a hash table, sorting, or repeated searches.

Sortedness changes the evidence available to us. Every occurrence of the same value is adjacent:

... -> 2 -> 2 -> 2 -> 3 -> ...

So the global question—

How many times does this value appear?

—becomes a local question—

How long is this contiguous run?

That is the recognition cue: when equal values are guaranteed to be adjacent, classify each run before linking it into the result.

The first node of a run cannot be linked immediately. At that moment, you do not yet know whether the run ends after one node or continues into duplicates. The algorithm must temporarily hold that decision.

This is why the usual approach for the neighboring problem is wrong here. In that problem, seeing 3 -> 3 lets you skip the second node and keep the first. Here, seeing 3 -> 3 means the first 3 was also invalid. You must remove the whole run.

The pointer pattern is best described as predecessor-and-scan:

• the predecessor anchors the retained prefix;
• the scan classifies the next run;
• the link changes only after classification.

Fast and Slow Pointers are not the primary pattern here. There is no midpoint, cycle, or unequal-rate traversal. The two pointers have different responsibilities: one maintains a stable boundary, and one explores a complete block.

Use a baseline to expose the optimization

A straightforward solution can use a frequency map:

1. Traverse the list and count every value.
2. Traverse it again.
3. Relink only nodes whose count is exactly one.

That approach is correct and often easy to explain. It uses O(n) auxiliary space, though, and separates the information-gathering pass from the mutation pass.

You could also repeatedly scan forward from each node to find equal values. That reprocesses the same duplicate runs and makes pointer ownership harder to reason about. A run of ten equal nodes should be classified once, not rediscovered from multiple starting positions.

The sorted input gives us a better option. We do not need global storage because adjacency is already encoding the frequency information locally. Scan each contiguous run once, then rewire one link.

Sorted adjacency replaces global frequency storage with local evidence. That trade only works because the input contract guarantees sorted order.

The optimized solution uses:

• a constant-size dummy node;
• prev, the last node proven to survive;
• curr, the first node in the next unclassified run.

The list itself supplies all other storage.

Derive the predecessor-and-scan invariant

Start with a dummy node:

dummy -> head

Set:

prev = dummy
curr = head

The dummy is not part of the answer. It simply gives the original head a predecessor, so deleting a head run uses the same operation as deleting a run in the middle.

The state has a precise meaning:

• prev is the last node known to belong in the output.
• prev.next is the first node not yet classified.
• curr is the first node of the current run.

Now scan forward while the next node has the same value as curr:

while curr.next and curr.next.val == curr.val:
    curr = curr.next

When this loop stops, curr is the final node of the current run.

There are two cases.

Case 1: the run contains one node

If:

prev.next is curr

then the predecessor still points directly to curr. No node was skipped, so the run has length one. It is safe to retain:

prev = curr

Case 2: the run contains duplicates

If:

prev.next is not curr

then curr moved forward during the scan. The run had at least two nodes. Every node in it must disappear.

Bypass the run:

prev.next = curr.next

Do not move prev. It must continue to represent the last retained node. Moving it across a discarded run would make the deleted nodes part of the supposedly safe prefix.

After either branch, advance curr to the node after the run:

curr = curr.next

The core invariant is:

Nodes from dummy through prev are retained and correctly linked. curr begins the first unclassified run. No retained link points into a run that has been classified as duplicate.

That invariant explains the algorithm more reliably than memorizing a pointer template. It tells you which pointer may move, when it may move, and why.

Prove classification and rewiring

The inner scan correctly finds the complete run because the list is sorted. If another node has the same value as curr, it must appear immediately after the current run. There cannot be a matching occurrence hidden later behind a different value.

For a singleton run, prev.next is curr remains true. Advancing prev adds exactly that one original node to the known-good prefix.

For a duplicate run, prev.next is curr is false because curr advanced over at least one successor. Setting prev.next = curr.next skips the run's first node and every node scanned after it. The suffix remains reachable through the node after the run.

The dummy node handles two boundary cases without special code:

• If the duplicate run begins at the original head, prev is still dummy, so dummy.next can skip the entire run.
• If every node is duplicated, dummy.next eventually becomes None.

Surviving nodes are never reordered. Each retained node remains connected to the next retained suffix in its original direction, so the output remains sorted.

Termination follows from forward movement. curr advances through every node either in the inner scan or when moving to the next run. It never moves backward, and the list is finite.

Dry-run the pointer state

Consider:

1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5

The important state transitions are:

Current run	prev before decision	Run end	Decision	prev after
1	dummy	first 1	retain	1
2	1	first 2	retain	2
3 -> 3	2	second 3	bypass run	2
4 -> 4	2	second 4	bypass run	2
5	2	first 5	retain	5

After the 3 run:

2 -> 4 -> 4 -> 5

The important detail is that prev remains at 2. The 3 nodes are gone, but the next candidate is now the 4 run.

After bypassing the 4 run:

2 -> 5

Finally, 5 is a singleton and gets retained:

1 -> 2 -> 5

Now examine a duplicate run at the head:

1 -> 1 -> 1 -> 2 -> 3

Initially:

dummy -> 1 -> 1 -> 1 -> 2 -> 3
prev = dummy
curr = first 1

The scan moves curr to the third 1. Since prev.next still points to the first 1, prev.next is curr is false. Set:

dummy.next = 2

The result becomes:

2 -> 3

prev never moved across the deleted head run.

For an all-duplicate input:

7 -> 7

the duplicate branch sets:

dummy.next = None

The returned result is empty. An empty input starts with curr = None, so the loop does nothing and dummy.next is already None.

Implement the Python solution

Assume the standard ListNode interface with val and next fields. The code follows the invariant directly:

from typing import Optional


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

        # Last node proven to survive.
        prev = dummy

        # First node in the next unclassified run.
        curr = head

        while curr:
            # Move curr to the final node in its equal-valued run.
            while curr.next and curr.next.val == curr.val:
                curr = curr.next

            if prev.next is curr:
                # The run has one node, so retain it.
                prev = curr
            else:
                # The run has duplicates, so bypass every node in it.
                prev.next = curr.next

            # Begin classifying the next run.
            curr = curr.next

        return dummy.next

The identity check is doing useful work:

prev.next is curr

It does not merely compare values. It asks whether the predecessor still points directly to the current run's first node. If yes, the scan did not move and the run is a singleton. If no, the scan crossed at least one equal-valued successor, so the entire run must be removed.

The mutation order matters:

1. Finish scanning the run.
2. Decide whether to retain or bypass it.
3. Move curr to the next run.
4. Move prev only when the current run survived.

Returning head would be incorrect. The original head may have belonged to a duplicate run. The answer is always dummy.next.

Complexity, edge cases, and failure modes

Complexity

The outer loop processes one run at a time. The inner loop advances curr through duplicate nodes, but those nodes are not scanned again later. Across the complete algorithm, curr moves forward at most once per node.

Therefore:

• Time: O(n)
• Auxiliary space: O(1)

The dummy node and a fixed number of pointers use constant space. The existing linked list is modified in place.

Edge cases to test

Run the implementation against:

• an empty list: [];
• a singleton list: [5];
• a list with no duplicates: [1, 2, 3];
• one duplicate run in the middle: [1, 2, 2, 3];
• a duplicate run at the head: [1, 1, 2, 3];
• a duplicate run at the tail: [1, 2, 3, 3];
• multiple adjacent duplicate runs: [1, 1, 2, 2, 3];
• a run of three or more equal values: [4, 4, 4, 5];
• an input where every node is removed: [7, 7].

Common incorrect approaches

Skipping only later copies

This solves the neighboring problem. Given 3 -> 3, it keeps one 3. That violates this problem's contract, which requires removing both nodes.

Advancing prev through an unresolved run

If you move prev before knowing whether the run is unique, you may mark a duplicate node as retained. The predecessor must stay behind the run until classification is complete.

Returning the original head

A duplicate run may begin at the head. Return dummy.next, which reflects any head deletion.

Dereferencing curr.next without checking it

The run scan must guard curr.next before reading curr.next.val. The final node in a list has no successor.

Using recursion by default

A recursive formulation can work, but it adds call-stack space and does not improve the central reasoning. The iterative predecessor-and-scan version exposes the pointer obligations more clearly under interview pressure.

The transferable recognition rule

When a sorted linked list contains contiguous equal-valued runs and a run's fate depends on its full length, do not link the first node immediately.

Keep a stable predecessor behind the run. Scan to the run's end. Classify first. Then either advance the predecessor across a singleton or bypass the entire duplicate block.

That is the reusable move:

Stable predecessor. Complete run scan. Decide before linking.

On the next pointer-rewiring problem, look for the same structural signal. If local adjacency tells you the whole block, process the block as a unit—and make every pointer movement answer an invariant you can state out loud.