DSA sheet · Linked List · Merge / Sort pattern

Remove Duplicates from Sorted List II

The harder sister of Problem 19. There, we kept one copy of every value. Here, any value that appears more than once must disappear completely, every copy of it. The teacher first solves it with a hash map of frequencies (and shows a small off-by-one bug while writing values back), then builds the O(1)-space answer from scratch, discovering one by one why we need a previous pointer, why we need a dummy node, why there's a loop inside the loop, and why the previous pointer moves in two different ways.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked lists from scratch, deleting a block, the dummy node
• Part A · Brute force: frequency map + overwrite
• Part B · Optimal: prev + curr + dummy, in place
• Part C · Revision page

Part 0 · Before starting

Nodes, head, None

A linked list is a chain of nodes. Each node has a value (val) and a link to the next node (next). The last node points to None. The head is the first node; an empty list is head = None.

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

  [1] → [2] → [3] → [3] → [4] → [4] → [5] → None
   ↑
  head

Walking, and no index access

We walk with a separate pointer, curr = curr.next, so we never lose track of the start (the teacher always makes this "alias"). There's no list[i]; reaching position i means walking i steps, O(n). So a node can't "look back" at the node before it: if we'll need the previous node, we must carry a pointer to it ourselves. That's the heart of this problem.

Save next before you change a pointer

Overwriting node.next loses whatever it pointed to unless another pointer still holds it. Below, when we write prev.next = curr.next, the node we want to keep is read from curr.next in the same line, so nothing we need is lost; only the duplicates become unreachable.

Deleting a whole block of nodes

To delete a run of nodes, point the node just before the run to the node just after it. One assignment removes the whole block:

  [2] → [3] → [3] → [4] → ...
   ↑                 ↑
  prev       node after the block

  prev.next = (node after the block)

  [2] ─────────────→ [4] → ...      both 3s are gone

Tool: the dummy node

A dummy is a fake node we put in front of the head: dummy = ListNode(0, head). Why? In this problem the head itself might be deleted (in 1 → 1 → 1 → 3 the answer starts at 3). Without a dummy, deleting the first nodes would need special code to "change the head". With a dummy, the first real node has a node before it like every other node, so the same prev.next = … line works everywhere, and at the end the true head is always dummy.next (even if that's None because everything was deleted).

Part A · Brute force: frequency map + overwrite

LeetCode 82

1The question in simple words

You get the head of a sorted linked list. Delete all nodes whose value appears more than once, leaving only values that appear exactly once. Return the (still sorted) list.

  input:  [1] → [2] → [3] → [3] → [4] → [4] → [5] → None
  output: [1] → [2] → [5] → None

  input:  [1] → [1] → [1] → [2] → [3] → None
  output: [2] → [3] → None              ← the head itself was deleted

2What the constraints tell us

• Number of nodes: 0 to 300. 0 is allowed → base case for an empty list. The teacher repeats: the constraints decide what base case you must write, so always read them.
• 300 is very small → no TLE worry. But we still want to remove the extra space.
• The list is sorted ascending → copies of a value sit next to each other (used in Part B).

3Intuition: count, then keep the count-1 values

"Duplicate" means "frequency more than 1". So count how many times each value appears. Then go through the values and keep only those with count exactly 1.

For 1, 2, 3, 3, 4, 4, 5: counts are 1→1, 2→1, 3→2, 4→2, 5→1. Keep 1, 2, 5.

4Building the logic

Fill the map

Walk the list. For each value: freq[v] = freq.get(v, 0) + 1. The first time a value appears, it isn't in the map, so get gives the default 0, and we store 1. The second 3 reads 1 and stores 2.

Collect the unique values

Walk the list again and append curr.val to kept when freq[curr.val] == 1. (You could loop over the map instead. In Python a dict remembers insertion order, and we inserted in sorted list order, so that also gives sorted output. In Java a HashMap has no order, which is why walking the list is the safer habit.)

If nothing is kept

Example 1 → 1 → 1 → 2 → 2 → 3 → 3: counts are 3, 2, 2, so kept is empty. There's nothing to build; return None right away.

Write back, and the off-by-one bug

Like Problem 19, overwrite the first len(kept) nodes with the kept values, then end the list. The teacher's first attempt: write a value, move curr, repeat; after the loop set curr.next = None. But after writing the last value, curr has already moved one node further:

  kept = [1, 2, 5]
  after writing 3 values:  [1] → [2] → [5] → [3] → [4] → [4] → [5] → None
                                             ↑
                                    curr is HERE (one too far)

  curr.next = None  →  [1] → [2] → [5] → [3] → None     wrong: an extra 3

Her fix: keep a prev pointer one node behind curr (set prev = curr just before moving curr). After the loop, prev is on the last written node, so prev.next = None cuts in the right place.

  [1] → [2] → [5] ✂ [3] → [4] → [4] → [5]
               ↑     ↑
             prev   curr          prev.next = None  →  [1] → [2] → [5] → None ✓

5Approach steps

1. If head is None → return None.
2. Count every value in a dict.
3. Walk the list; collect values with count 1 in kept.
4. If kept is empty → return None.
5. Overwrite the first len(kept) nodes, tracking prev; then prev.next = None. Return head.

6Code (Python)

class Solution:
    def deleteDuplicates(self, head):
        if head is None:
            return None

        freq = {}
        curr = head
        while curr is not None:                     # count each value
            freq[curr.val] = freq.get(curr.val, 0) + 1
            curr = curr.next

        kept = []
        curr = head
        while curr is not None:                     # keep count-1 values, in order
            if freq[curr.val] == 1:
                kept.append(curr.val)
            curr = curr.next

        if not kept:                                # everything was duplicated
            return None

        prev = None
        curr = head
        for v in kept:                              # overwrite in place
            curr.val = v
            prev = curr
            curr = curr.next
        prev.next = None                            # cut after the last written node
        return head

7Code line by line

8Dry run: 1, 2, 3, 3, 4, 4, 5

9Complexity & remember

• Time O(n): three passes at most (count, collect, overwrite).
• Space O(n): the map, plus the kept list. You can skip the kept list by building nodes while reading the map, but the map is still there. That's why this is the brute force.

Part B · Optimal: prev + curr + dummy, in place

1The question in simple words

Same question, but with no extra space: only a few pointers, changing links in the existing list. The teacher builds this one "as if she had never seen it", so let's follow her discoveries in order.

2What the constraints tell us

• Sorted → copies form one block of neighbours, so "is this a duplicate?" = "does it equal its neighbour?"
• 0 nodes → with a dummy node the loop simply doesn't run and we return dummy.next = None; no separate check needed.

3Intuition: cut out whole blocks

Think of the sorted list as blocks of equal values: [1] [2] [3 3] [4 4] [5]. A block of size 1 stays. A block of size 2 or more is cut out entirely, by linking the node before the block to the node after it. So at every moment we need: a pointer to the last node we've decided to keep (prev) and a pointer that scans forward (curr).

4Building the logic, discovery by discovery

Example: 1 → 2 → 3 → 3 → 4 → 4 → 5.

Discovery 1: compare curr with curr.next, both must exist

As in Problem 19, a duplicate is found by checking curr.val == curr.next.val. Before reading curr.next.val, curr.next must not be None (Java would throw a null pointer exception, Python an AttributeError). 1 vs 2: different, move. 2 vs 3: different, move. 3 vs 3: same!

Discovery 2: Problem 19's trick leaves one copy behind

If we do curr.next = curr.next.next like before, the second 3 goes, and curr (first 3) now sees 4: different, move on. But the first 3 is still in the list, and this problem wants it gone too. To unlink that first 3, we need the node before it (the 2), and a list can't walk backwards. So we need a prev pointer that trails behind.

Discovery 3: the head can be deleted → use a dummy

Take 1 → 1 → 1 → 3. All the 1s go; the answer starts at 3. So "return head" is wrong whenever the head's value is duplicated. Rather than tracking "what's the new head?" with extra if/else, the teacher's preferred fix: a dummy before the head, prev starting at the dummy, and return dummy.next. If everything is deleted, dummy.next is None, which is right; if the first few blocks are deleted, dummy.next points to the first survivor.

  [0] → [1] → [2] → [3] → [3] → [4] → [4] → [5] → None
 dummy   ↑
  prev  curr

Discovery 4: skipping a block needs a loop, not a single step

When curr and curr.next match, move curr forward: curr = curr.next. What if there were three 3s? We'd check again and move again. "Repeat while true" means a while loop: while curr.next and curr.val == curr.next.val: curr = curr.next. When it stops, curr is on the last node of the block (the second 3), because the next node (4) is different.

  [0] → [1] → [2] → [3] → [3] → [4] → [4] → [5]
               ↑            ↑
              prev         curr  (last 3; curr.next = 4 differs)

Discovery 5: after the block, link prev past it

The inner loop moved only curr, never prev. curr itself is part of the duplicate block, so it must go too. prev (the 2) should now point to the node after curr: prev.next = curr.next. Then curr steps forward: curr = curr.next (onto the first 4). prev stays on 2, because we don't yet know whether 4 survives.

  [0] → [1] → [2] ───────────→ [4] → [4] → [5]
               ↑                ↑
              prev             curr

Next round: 4 vs 4 match → inner loop takes curr to the second 4 → prev.next = curr.next links 2 → 5 → curr moves to 5. prev is still on 2. Good: that's exactly why prev must not move after a deletion. The next block could also be a duplicate block, and prev must stay on the last node that's known to be kept.

Discovery 6: why the if around the while? Because prev moves in two ways

If curr and curr.next are different (no duplicate starts here), curr is a survivor. Then prev should take a normal step forward along with curr. That's the else branch, and it's why the teacher wraps the inner while in an if: she needs an else.

• Movement 1, linear: no duplicate → prev = prev.next, and curr steps too.
• Movement 2, jump: duplicate block → prev doesn't move, but its next link jumps over the whole block.

To show this, she imagines a 6 after the 5: at 5, 5 vs 6 differ → prev steps onto 5, curr onto 6; then 6 has no next → else again → prev onto 6, curr onto None → stop.

Discovery 7: the outer loop and the return

Repeat everything while curr is not None (if curr is None there's nothing left to check). Afterwards return dummy.next, never head, because the head might have been cut out.

5Approach steps

1. dummy = ListNode(0, head), prev = dummy, curr = head.
2. While curr is not None:
   • if curr.next exists and has the same value: move curr to the last node of this block (inner while), then prev.next = curr.next;
   • else: prev = prev.next;
   • in both cases: curr = curr.next.
3. Return dummy.next.

6Code (Python)

class Solution:
    def deleteDuplicates(self, head):
        dummy = ListNode(0, head)     # in front of head (head may be deleted)
        prev = dummy                  # last node we are sure to keep
        curr = head                   # scanner

        while curr is not None:
            if curr.next is not None and curr.val == curr.next.val:
                # walk to the last node of this duplicate block
                while curr.next is not None and curr.val == curr.next.val:
                    curr = curr.next
                prev.next = curr.next     # jump over the whole block
            else:
                prev = prev.next          # curr survives: prev steps normally
            curr = curr.next

        return dummy.next

7Code line by line

8Dry run: 1 → 2 → 3a → 3b → 4a → 4b → 5

  start:        [0] → [1] → [2] → [3a] → [3b] → [4a] → [4b] → [5] → None
               prev  curr

  round 3:      [0] → [1] → [2] → [3a] → [3b] → [4a] → [4b] → [5]
                             prev          curr  (after inner loop)
                2.next = 4a:
                [0] → [1] → [2] ─────────────→ [4a] → [4b] → [5]
                             prev               curr

  round 4:      [0] → [1] → [2] ──────────────────────────→ [5] → None
                             prev                            curr

  round 5:      prev → 5, curr → None.  Answer: [1] → [2] → [5] → None

When the head is deleted: 1a → 1b → 1c → 2 → 3.

All duplicates, e.g. 1 → 1 → 2 → 2: round 1 sets dummy.next = 2a, round 2 sets dummy.next = None → return None ✓.

9Complexity & remember

• Time O(n): the inner loop doesn't make it O(n²). Every step of either loop moves curr forward by one node, and curr only goes forward, so in total curr makes at most n moves.
• Space O(1): a dummy node and two pointers. No map, no list.

Part C · Revision page

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

def build(vals):
    dummy = tail = ListNode()
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.deleteDuplicates(build([1, 2, 3, 3, 4, 4, 5]))))  # [1, 2, 5]
print(to_list(s.deleteDuplicates(build([1, 1, 1, 2, 3]))))        # [2, 3]
print(to_list(s.deleteDuplicates(build([1, 1, 2, 2]))))           # []
print(to_list(s.deleteDuplicates(build([]))))                     # []

Based on this video: Remove Duplicates from Sorted List II