Remove Linked List Elements — Dummy Head Pattern for Clean Deletion

Problem Statement#

Given the head of a linked list and an integer val, remove all the nodes of the linked list that have Node.val == val, and return the new head.

Constraints:

• The number of nodes in the list is in the range [0, 10^4]
• 1 <= Node.val <= 50
• 0 <= val <= 50

Example 1:

Input:  head = [1, 2, 6, 3, 4, 5, 6], val = 6
Output: [1, 2, 3, 4, 5]

Example 2:

Input:  head = [], val = 1
Output: []

Example 3:

Input:  head = [7, 7, 7, 7], val = 7
Output: []
Explanation: All nodes are removed — result is an empty list.

Why This Problem Matters#

Remove Linked List Elements (LeetCode 203) teaches you the most important structural trick in linked list problems: the dummy head (sentinel) node. Google and Amazon include this problem in their interview pools because it exposes whether candidates handle the edge case of deleting the head node cleanly or resort to messy branching.

The core challenge: in standard linked list deletion, you need access to the predecessor node (prev.next = node.next). But when the node to delete is the head, there is no predecessor. Without a dummy node, you'd need special logic to handle this case. With a dummy node placed before the head, the head becomes just another interior node — no special case required.

This dummy head pattern appears everywhere: merge two sorted lists, partition list, remove Nth node from end — virtually every problem that might delete the head node uses this trick. Internalizing it here means you automatically apply it correctly in harder problems.

The problem also tests your ability to handle three edge cases simultaneously: empty list, all nodes match the target value, and target value only appears at the head.

The Core Insight#

Create a dummy node with any value (dummy.val = 0) and point it to the original head: dummy.next = head. Start a cursor curr at the dummy node. Now you never need to delete curr itself — you always look ahead at curr.next.

At each step: if curr.next.val == val, skip curr.next by setting curr.next = curr.next.next. If not, advance curr = curr.next. At the end, return dummy.next — which is the new head of the filtered list.

This pattern unifies head deletion with interior deletion. The dummy is the "before-the-head" sentinel that ensures every real node has a predecessor.

Visual Dry Run#

Input: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6, val = 6

Return dummy.next = 1.

Output: 1 -> 2 -> 3 -> 4 -> 5

All-match case: 7 -> 7 -> 7, val = 7

Return dummy.next = None. Correct — empty list.

Solution (Optimal)#

Python#

def removeElements(head, val):
    dummy = ListNode(0)   # sentinel before the head
    dummy.next = head
    curr = dummy          # cursor always points to node BEFORE the check
 
    while curr.next:
        if curr.next.val == val:
            curr.next = curr.next.next  # skip the matching node
        else:
            curr = curr.next            # advance only when not skipping
    
    return dummy.next  # new head (dummy.next updated if original head was removed)

Time complexity: O(n) — each node examined once.

Space complexity: O(1) — dummy node and cursor pointer only.

JavaScript#

var removeElements = function(head, val) {
    const dummy = new ListNode(0);
    dummy.next = head;
    let curr = dummy;
 
    while (curr.next !== null) {
        if (curr.next.val === val) {
            curr.next = curr.next.next;  // skip
        } else {
            curr = curr.next;            // advance
        }
    }
 
    return dummy.next;
};

Recursive variant:

def removeElements(head, val):
    if not head:
        return None
    head.next = removeElements(head.next, val)
    return head.next if head.val == val else head

Complexity:

Common Mistakes#

1. Not using a dummy head — writing special head logic instead. Without a dummy, you need: "while head and head.val == val: head = head.next" before the main loop. This is error-prone and verbose. The dummy head eliminates this completely.

2. Advancing curr after a skip. When curr.next.val == val, you set curr.next = curr.next.next but do not advance curr. The new curr.next might also match! If you advance after a skip, you miss consecutive matching nodes.

3. Using curr.next = curr.next.next when curr.next.next could be None. Setting curr.next = None is valid — it just terminates the list. There's no null pointer error here. But be careful: if you try to access curr.next.next.val without checking, that's the bug. The skip itself is safe.

4. Returning head instead of dummy.next. If the original head matches val, it's been removed. head still points to the old (deleted) node. Always return dummy.next.

5. Forgetting to handle the empty list. If head = None, dummy.next = None, curr = dummy, and curr.next is None — the while loop never executes, and you return dummy.next = None. Correct, and requires no special case.

Interview Tips#

1. State the dummy head pattern explicitly: "I'll use a dummy sentinel node before the head. This ensures the head node is treated the same as any other node — no special case needed."

2. Trace the all-match case: [7, 7, 7] with val = 7. Show that the cursor stays at dummy throughout and dummy.next becomes None.

3. Explain why you don't advance after a skip: "After skipping, the new curr.next might also match. I only advance when the current next is safe to keep."

4. Mention the recursive version as a follow-up if time allows — it's elegant and shows you can think recursively.

5. Connect to harder problems: "This dummy head pattern is used in merge two sorted lists, remove Nth from end, and partition list — it's a reusable tool."

Follow-up Questions#

Q: Can you solve it without a dummy head? Yes, but with more code. You'd pre-process the head: while head and head.val == val: head = head.next. Then proceed with the standard predecessor-skip logic. The dummy head eliminates this pre-processing.

Q: What if you need to remove nodes that satisfy a general condition (predicate), not just equal to val? Replace curr.next.val == val with condition(curr.next). Same pattern, more general. This is the "filter" operation on a linked list.

Q: What is the recursive approach? Base case: empty list returns None. Recursive step: head.next = removeElements(head.next, val). Then return head.next if head.val == val, else return head. Elegant but O(n) stack space.

Q: What if val can appear at most once? The same code works — it handles one occurrence. The code doesn't assume multiple occurrences; it just handles them if present.

Q: How does this relate to filtering in functional programming? This is a destructive filter operation on a linked list: keep nodes where val != target. The recursive version most closely mirrors the functional filter definition.

Key Takeaways#

• The dummy head sentinel node before the real head is the universal pattern for problems that might delete the head.
• When you skip a node (curr.next = curr.next.next), do not advance curr — the new curr.next might also need removal.
• Always return dummy.next, not the original head, because head may have been removed.
• This pattern handles all edge cases automatically: empty list, all nodes removed, only head removed.
• Time is O(n), space is O(1) for the iterative approach.
• The recursive version is O(n) space — prefer iterative for large lists or when the interviewer asks about stack overflow concerns.