Community Problem
Remove Linked List Elements
Difficulty: Easy
Delete every node in a singly-linked list whose value matches a target, with a sentinel/dummy node that makes the head case fall out of the general loop.
Remove Linked List Elements
Delete every node in a singly-linked list whose value matches a target, with a sentinel/dummy node that makes the head case fall out of the general loop.
By @jameszhang
January 17, 2026
·
Updated May 18, 2026
699 views
19
4.5 (9)
Used this in mock interviews dozens of times because it's the cleanest place to drill the dummy/sentinel pattern that EVERY linked-list problem with deletion needs. The mistake I see weekly: special-casing the head with an if chain at the top instead of attaching a sentinel and letting one loop handle every case.
Remove Linked List Elements
Given the head of a singly-linked list and an integer val, remove every node whose Node.val == val and return the new head. The relative order of remaining nodes must be preserved.
Examples
Example 1:
- Input:
head = [1, 2, 6, 3, 4, 5, 6],val = 6 - Output:
[1, 2, 3, 4, 5] - Explanation: Both 6s are removed.
Example 2:
- Input:
head = [7, 7, 7, 7],val = 7 - Output:
[] - Explanation: All four nodes match and are removed.
Example 3:
- Input:
head = [],val = 1 - Output:
[] - Explanation: Empty list stays empty.
Example 4:
- Input:
head = [1, 2, 3],val = 4 - Output:
[1, 2, 3] - Explanation: No node matches, list unchanged.
Constraints
- The number of nodes in the list is in the range
[0, 10^4]. 1 <= Node.val <= 500 <= val <= 50
Follow-up
Why is the dummy / sentinel pattern strictly cleaner than a head-special-case loop? The sentinel makes the head's predecessor explicit, so the deletion code is a single prev.next = prev.next.next regardless of whether the deleted node is the head or interior.
Solution
Hints
Approach
The pattern is the textbook dummy/sentinel for any linked-list operation that may modify the head. We allocate one extra node dummy whose next points at the real head. Now the head case has the same shape as any interior case: prev (initially dummy) is the predecessor of the candidate, and deletion is prev.next = cur.next.
Key insight
Without a sentinel, deleting the head requires head = head.next (different syntax from prev.next = cur.next), AND the head may need to be deleted multiple times in a row if it matches consecutively, requiring a separate pre-loop. With a sentinel, those special cases vanish. One loop, two cases (match: skip; no match: advance), one return.
Algorithm
- Allocate
dummy = new ListNode(0, head). - Initialize
prev = dummy,cur = head. - While
cur !== null:- If
cur.val === val: skip withprev.next = cur.next. - Else: advance
prev = cur. - Always advance
cur = cur.next.
- Return
dummy.next(the new head).
Complexity
Metric Value
------ -----
Time O(n)
Space O(1) auxiliaryA single pass; the dummy is one node of overhead.
Why it works
The sentinel turns the doubly-special head case into a uniform interior case. The invariant during the loop is: prev.next is the next node we have not yet inspected, and every node before prev.next has already been processed correctly. Deleting via prev.next = cur.next preserves the invariant because cur is detached from the chain of survivors. Advancing cur = cur.next always (whether we deleted or kept) ensures progress and correct re-linking.
Pitfalls
- Updating
cur = cur.nextBEFORE the deletion: at that pointcur.nextmay already have been re-pointed by a previousprev.next = cur.next, which is fine, but if the order is wrong and you advanceprevAFTER deleting, you skip a comparison. - Forgetting to advance
curinside the deletion branch. The cleanest layout puts thecur = cur.nextoutside theif/else. - Using a recursive solution: also valid and elegant (
return headif null, otherwisehead.next = removeElements(head.next, val); return head.val === val ? head.next : head;). On lists up to10^4it works in JS but the iterative version is friendlier under interview pressure.
Solution Code