Remove Linked List Elements — Solution

Problem

Given a linked list and a target value, remove every node whose value equals the target and return the updated list. The trick is that the head itself might need to be removed.

[1,2,6,3,4,5,6]

• Input: head = [1,2,6,3,4,5,6], val = 6
• Output: [1,2,3,4,5]
• Explanation: Both 6s are removed; the rest of the list stays in order.

Intuition

Walk the list and whenever the next node holds the target value, skip over it by rewiring the current node's pointer. The only wrinkle is the head: if the first node is a target, there is nothing before it to rewire. A dummy sentinel node planted before the head eliminates this special case entirely, making every removal uniform.

Solution — Iterative with Dummy Node

Attach a sentinel node before the head, then scan forward. When current.next holds the target value, bypass it; otherwise advance current. Return dummy.next as the new head.

1. Create a dummy node pointing to head.
2. Set current = dummy.
3. While current.next exists:
   • If current.next.val == val, set current.next = current.next.next (bypass the target node).
   • Otherwise, advance current = current.next.
4. Return dummy.next.

1def removeElements(head, val):
2    dummy = ListNode(0)
3    dummy.next = head          # sentinel sits before the real list
4    current = dummy
5    while current.next:
6        if current.next.val == val:
7            current.next = current.next.next  # bypass the target node
8        else:
9            current = current.next  # only advance when keeping the node
10    return dummy.next          # new head, which may differ from original

Time: O(n) — every node is visited exactly once.

Space: O(1) — only the dummy node is allocated; no extra data structures.

Complexity Summary

Common Mistakes

• Skipping the dummy node and writing a separate while (head != null && head.val == val) head = head.next prefix — the dummy node removes this entirely.
• Advancing current after a removal — after bypassing a target node, current.next is now a new unchecked node that could also be the target, so the loop must re-check before advancing.
• Returning head instead of dummy.next — if the original head nodes were removed, head is stale and points to a deleted node.
• In C++: not deleting removed nodes — the bypassed node is still heap-allocated; forgetting delete leaves a memory leak.
• Confusing removal with advancement — the else branch is critical; removing a node is not the same as moving forward, and the two are mutually exclusive per iteration.

Related Problems

• reverse-linked-list — the same pointer-walking pattern applied to full reversal
• remove-duplicates-from-sorted-list — same dummy-node traversal with a different skip condition
• remove-nth-node-from-end-of-list — deletion from the end using a two-pointer gap
• delete-the-middle-node-of-a-linked-list — single-deletion variant using fast/slow pointers
• palindrome-linked-list — full-pass traversal and structural comparison