Remove Duplicates from Sorted List II

Solving tips

Because the list is sorted, all copies of a value form one consecutive run, so 'is duplicated' is decidable by peeking one node ahead.
Use a dummy node before the head (the head itself may be deleted) and a prev pointer to the last node guaranteed to survive.
When you detect a run, skip the entire run and set prev.next past it, but do NOT advance prev, since the next node may start another duplicate run.
Aim for O(n) time, O(1) space; don't confuse this with Remove Duplicates I, which keeps one copy.

Problem

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

This is the stricter sibling of “Remove Duplicates I”, where you keep one copy of each value; here a duplicated value is wiped out 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 go — including the head.
Input: head = [1, 1] → Output: [] Everything is a duplicate; 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

Hint 1

Because the list is sorted, all copies of a value sit in one consecutive run. How do you tell whether a run has length 1 or more without counting the whole list first?

Hint 2

The head itself might be deleted (example 2). What standard trick gives every deletable node a predecessor?

Hint 3

Use a dummy node before the head and keep `prev` = last node known to survive. Look at `prev.next`: if its value repeats, advance a scanner past the whole run and set `prev.next` to the node after the run — without moving `prev`. If it doesn't repeat, `prev` advances.

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

class Solution:
    def deleteDuplicates(self, 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 — its real sin is ignoring the sortedness, spending O(n) memory on information the ordering gives you for free.

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

Insight: in a sorted list every duplicated value forms one consecutive run, so “appears more than once” is decidable locally: peek 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.

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

class Solution:
    def deleteDuplicates(self, 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]:

node	run?	action	list via dummy
1	no	prev=1	1→2→3→3→4→4→5
2	no	prev=2	unchanged
3	yes (3,3)	skip both, prev.next=4	1→2→4→4→5
4	yes (4,4)	skip both, prev.next=5	1→2→5
5	no	prev=5	1→2→5

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

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

Approach 3 — Recursion

Insight: the same run logic phrased self-referentially: if the head starts a run, the answer is deleteDuplicates(first node after the run); otherwise it’s the head followed by the answer for the rest. Elegant, and 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

class Solution:
    def deleteDuplicates(self, 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 self.deleteDuplicates(node)   # drop the whole run
        head.next = self.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) — fine for n <= 300, but the iterative version wins 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.