Remove Duplicates from Sorted List II

Problem

You are given the head of a sorted singly linked list. Delete every node whose value appears more than once, removing all occurrences of any duplicated value rather than only the extra copies. Return the head of the resulting list, which must remain sorted.

This differs from “Remove Duplicates I”, where you keep one copy of each value. Here any value that appears more than once is removed entirely.

Examples

• Input: head = [1, 2, 3, 3, 4, 4, 5] → Output: [1, 2, 5] 3 and 4 each appear twice, so every 3 and 4 is deleted.
• Input: head = [1, 1, 1, 2, 3] → Output: [2, 3] The value 1 appears three times, so all three nodes are removed, including the head.
• Input: head = [1, 1] → Output: [] Both values are duplicates, so the result is the empty list.

Constraints

• 0 <= n <= 300 where n is the number of nodes.
• -100 <= Node.val <= 100.
• The list is sorted in non-decreasing order — this is what lets duplicates be detected locally, as consecutive runs.

Think about it first

TL;DR

One pass with a dummy node: skip whole runs of repeated values, keep singletons — O(n) time, O(1) space.

Approach 1 — Brute force: count first, filter second

Two passes with a counter: tally every value, then rebuild the list keeping only values whose count is exactly 1.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
    counts: Dict[int, int] = {}
    node = head
    while node:
        counts[node.val] = counts.get(node.val, 0) + 1
        node = node.next
    dummy = ListNode()
    tail = dummy
    node = head
    while node:
        if counts[node.val] == 1:
            tail.next = node
            tail = node
        node = node.next
    tail.next = None
    return dummy.next

Time O(n), space O(n) for the counter. With n <= 300 it passes easily, but it ignores the sortedness and spends O(n) memory on information the ordering already provides.

Approach 2 — One-pass run skipping with a dummy (optimal)

In a sorted list every duplicated value forms one consecutive run, so “appears more than once” can be decided locally by peeking one node ahead. Keep prev pointing at the last node guaranteed to survive. If the run starting at prev.next has length >= 2, bypass the entire run in one splice. prev itself must not move, because the node right after the run might start another duplicate run. A dummy node in front of the head gives the head a predecessor, so head deletion needs no special case.

flowchart LR
  dummy["dummy"] --> n1["1"] --> n2["2"] --> a3["3"] --> b3["3"] --> a4["4"] --> b4["4"] --> n5["5"]
  prev(["prev"]) -.-> n2
  n2 -. splice past run .-> a4

prev sits at 2. The run 3 → 3 is skipped by setting prev.next to the node after it, and prev stays at 2 so the next run 4 → 4 can also be removed.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    prev = dummy
    node = head
    while node:
        if node.next and node.next.val == node.val:
            run_val = node.val
            while node and node.val == run_val:
                node = node.next     # skip the whole run
            prev.next = node         # splice it out; prev stays put
        else:
            prev = node              # singleton survives
            node = node.next
    return dummy.next

Walkthrough on [1, 2, 3, 3, 4, 4, 5]:

Output [1, 2, 5]. prev stayed at 2 across both deletions, which is why it only advances on singletons.

Time O(n): node only ever moves forward. Space O(1).

Approach 3 — Recursion

The same run logic phrased recursively: if the head starts a run, the answer is deleteDuplicates(first node after the run); otherwise it is the head followed by the answer for the rest. This is a common interview follow-up (“can you write it recursively?”).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def deleteDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    if head.val == head.next.val:
        node = head.next
        while node and node.val == head.val:
            node = node.next
        return deleteDuplicates(node)   # drop the whole run
    head.next = deleteDuplicates(head.next)
    return head

Walkthrough on [1, 1, 1, 2, 3]: head 1 starts a run — skip to node 2 and recurse. Head 2 is a singleton — keep it, recurse on [3]. [3] returns itself. Result 2→3.

Time O(n), space O(n) for the call stack (each frame consumes at least one node). This is fine for n <= 300, but the iterative version is preferable on unbounded input.

Common pitfalls

• Advancing prev after deleting a run — the next run may also need deleting, and prev must still be the splice point (see the double deletion in the walkthrough).
• Solving the wrong problem: keeping one copy per value is Remove Duplicates I; here duplicated values vanish entirely.
• No dummy node: [1, 1, 2] deletes the head, and returning the right head without a dummy takes ugly special-casing.
• Comparing node.next.val without first checking node.next is not None — instant crash on the last node.

Pattern takeaway

Two staples combine here. First: any deletion that might remove the head calls for a dummy predecessor node. Second: in sorted sequences, properties like “is duplicated” become run-local — process a whole run per step and the pass stays linear. Keep a “last certain survivor” pointer and only advance it when the node ahead is proven safe.