LeetCode 203 – Remove Linked List Elements

Remove Linked List Elements is the problem Remove Duplicates from Sorted List set up. There the head could never be removed, so no dummy node was needed. Here it can — repeatedly — and the dummy head stops being a stylistic preference and becomes the thing that makes the code short.

The problem

Remove every node whose value equals a given target, and return the resulting list.

1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6,  val = 6   ->  1 -> 2 -> 3 -> 4 -> 5
[],                               val = 1   ->  []
7 -> 7 -> 7 -> 7,                 val = 7   ->  []    everything goes
1 -> 2 -> 2 -> 1,                 val = 2   ->  1 -> 1
6 -> 1 -> 6,                      val = 6   ->  1     head AND tail removed

The third example is the one to hold onto: the entire list can disappear, so the function must be able to return null even when handed a non-empty list.

Why a dummy head, here and not there

The rule from problem 83, stated again because this is the problem that proves it:

A dummy head is needed exactly when the head itself might be removed.

Removing duplicates keeps the first occurrence of every value, so the first node always survives. Removing by value has no such guarantee — and worse, the head can be removed several times in a row, as 7 → 7 → 7 → 7 shows. Without a dummy you need a loop before the main loop just to skip leading matches, and then the main loop again, and the two are almost the same code.

A dummy node pointing at the head makes every node — including the original head — have a predecessor. There is then exactly one case, and the answer is dummy.next, whatever it ended up being.

Java

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // Gives the original head a predecessor, so removing it needs no special case.
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode previous = dummy;

        while (previous.next != null) {
            if (previous.next.val == val) {
                previous.next = previous.next.next;   // unlink; do NOT advance
            } else {
                previous = previous.next;
            }
        }

        return dummy.next;    // not `head` -- the head may be gone
    }
}

Return dummy.next, never head. If the original head was removed, head still points at a node that is no longer in the list — and returning it gives back the deleted node plus everything that followed it, which on 6 → 1 → 6 with val = 6 returns 6 → 1. It looks almost right, which is the worst kind of wrong.

Not advancing after a removal is the same rule as problem 83, and for the same reason: the new previous.next has not been examined yet. 7 → 7 → 7 → 7 is the input that catches it.

Python

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head

        previous = dummy
        while previous.next:
            if previous.next.val == val:
                previous.next = previous.next.next    # unlink; do NOT advance
            else:
                previous = previous.next

        return dummy.next

The recursive version

This problem has an unusually clean recursion, because "remove from the rest of the list" is exactly the same problem:

    def removeElementsRecursive(self, head: ListNode, val: int) -> ListNode:
        if head is None:
            return None

        head.next = self.removeElementsRecursive(head.next, val)

        # Drop this node by returning what follows it -- no dummy needed, because
        # the caller receives whatever this call decides the new head is.
        return head.next if head.val == val else head

Three lines, no dummy, and the head problem evaporates: the recursion returns a head rather than mutating one, so "the head was removed" is just a different return value.

It is O(n) stack, which overflows on a list of a hundred thousand nodes. Give the iterative version, then offer this — and note the trade rather than presenting it as strictly better.

Complexity

Every node is examined once — either unlinked or stepped past — so the loop is linear despite having no explicit advance in one branch.

The pattern

The dummy head appears whenever the head is not guaranteed to survive:

Four out of five. The dummy is close to free — one allocation — and it removes an entire class of special case, which is why reaching for it by default is a reasonable habit as long as you can say when it is unnecessary.

What the interviewer is checking

• That the head can be removed, so a dummy earns its place.
• Returning dummy.next rather than head.
• Not advancing after a removal — 7 → 7 → 7 → 7 is the test.
• A list that empties completely.
• An empty list, and a list with no matches.
• That you can say why problem 83 did not need a dummy.