Remove Linked List Elements: Dummy Head Deletion

Remove Linked List Elements is LeetCode problem 203. You are given the head of a linked list and an integer val. Remove all nodes where Node.val == val and return the new head.

Example: [1, 2, 6, 3, 4, 5, 6] with val = 6 becomes [1, 2, 3, 4, 5]. An empty list returns empty. A list like [7, 7, 7, 7] with val = 7 returns empty.

The catch is that the target value might appear at the head of the list. If you delete the head, you need to return a different node as the new head. Handling this as a special case is messy. A dummy node eliminates the special case entirely.

The approach

Create a dummy node that points to the original head. Then use a prev pointer starting at the dummy node. At each step, look at prev.next:

• If prev.next.val == val, the next node needs to go. Set prev.next = prev.next.next to skip over it. Do not advance prev, because the new prev.next might also need to be removed.
• If prev.next.val != val, the next node is safe. Advance prev to prev.next.

Keep going until prev.next is null. Then return dummy.next, which is the new head.

The dummy node is the key insight. Because prev starts before the real head, you can delete the head node using the exact same logic as deleting any other node. No special cases needed.

Visual walkthrough

Trace through removing val = 6 from the list 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6 -> null. The dummy node (D, yellow) anchors the front. Watch the prev pointer (purple) as it walks through the list, skipping nodes that match the target value.

Notice how prev only advances when prev.next is safe. When a match is found, prev stays put and the matching node gets bypassed. This ensures consecutive matches are caught even if they appear back to back.

Python solution

def removeElements(head, val):
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    while prev.next:
        if prev.next.val == val:
            prev.next = prev.next.next
        else:
            prev = prev.next

    return dummy.next

Step-by-step explanation

1. Create the dummy node. It points to the original head. This gives you a stable anchor that never gets deleted.
2. Set prev = dummy. The prev pointer will always sit one node behind the node being examined.
3. Loop while prev.next exists. You are always checking the node ahead of prev, not prev itself.
4. If prev.next.val == val, splice it out with prev.next = prev.next.next. The node is effectively removed from the chain. prev stays where it is so the new prev.next gets checked on the next iteration.
5. If prev.next.val != val, the node is safe. Move prev forward by one.
6. Return dummy.next. The dummy itself is never part of the result. Its next pointer gives you the true head of the cleaned-up list.

Complexity analysis

Time: O(n). You visit each node exactly once. Every node is either skipped (removed) or passed over (prev advances). The total number of operations across all iterations is at most n.

Space: O(1). You only allocate one dummy node and one pointer variable. The removal happens in-place by rewiring existing pointers. No extra data structures are needed.

The building blocks

This problem is built from two core building blocks:

Dummy head for safe deletion. When a deletion might affect the head node, prepending a dummy node lets you treat every node uniformly. You never need a separate check for "is this the head?" The dummy absorbs that edge case.

This pattern appears in many linked list problems:

• Remove Duplicates from Sorted List II (LeetCode 82) deletes all nodes with duplicate values. A dummy head is essential because the original head might have duplicates.
• Partition List (LeetCode 86) builds two sublists with dummy heads, then merges them.
• Any problem where the head might be deleted benefits from this technique.

Pointer-based node removal. You keep a prev pointer one step behind the node under inspection. To remove a node, you set prev.next = prev.next.next. This is the fundamental linked list deletion operation.

This shows up everywhere:

• Remove Duplicates from Sorted List (LeetCode 83) uses the same prev.next = prev.next.next splice but checks for matching adjacent values instead of a target value.
• Remove Nth Node From End of List (LeetCode 19) finds the node to remove with a two-pointer gap, then splices it out the same way.

Once you have the dummy-head-plus-prev-pointer pattern in muscle memory, any linked list deletion problem becomes a variation of the same idea.

Edge cases

• Empty list (head is null). dummy.next is null from the start. The while loop never runs. Return null.
• All nodes match the target (e.g., [7, 7, 7, 7] with val = 7). Every node gets spliced out. prev never advances past the dummy. dummy.next ends up as null. Return null.
• No nodes match the target. prev advances through every node without splicing. The list is returned unchanged.
• Target is at the head. The dummy node handles this. prev is at the dummy, prev.next is the head, and it gets spliced out just like any other node.
• Target is at the tail. When prev reaches the second-to-last node, prev.next.val == val, so you set prev.next = prev.next.next (which is null). The tail is cleanly removed.

From understanding to recall

This is a short solution with simple logic. You will read it and feel confident. But in an interview, the details matter: do you create the dummy node before or after setting prev? Do you advance prev inside the if or the else? Do you return dummy.next or head?

These small decisions are exactly the kind of thing that slips under pressure. The fix is not to reread the solution. It is to type it from scratch, repeatedly, until the structure is automatic. Spaced repetition turns understanding into recall. After a few reps, you will not hesitate on any of those choices.

Related posts

• Remove Duplicates from Sorted List - Same pointer-based deletion technique, applied to removing duplicate values instead of a target value
• Reverse Linked List - Another fundamental linked list operation where pointer manipulation order determines correctness