You are given the head of a singly linked list and an integer val. Remove every node whose value equals val and return the head of the resulting list.
A node is removed by re-routing the list around it, so the nodes you keep stay in their original order. If every node matches — or the list is empty to begin with — return an empty list (a null head).
Matches can appear anywhere: at the front, in the middle, in a run of consecutive nodes, or at the very end.
delete the spliced-out node to avoid a leak, though the judge only checks the returned list.prev after a removal. Keep prev fixed and re-check the new prev.next, which may also match.dummy.next is already null, so the same code handles it with no special case.curr.val == val with any predicate; the sentinel-and-splice skeleton is unchanged. This generalizes to filtering a linked list in place.head.next to clean the tail, then return that tail if head.val == val, else attach head in front. Elegant, but it uses O(n) call-stack space.Input: head = [1,2,6,3,4,5,6], val = 6 Output: [1,2,3,4,5] Both nodes equal to 6 are removed; the survivors keep their order.
Input: head = [], val = 1 Output: [] An empty list stays empty.
Input: head = [7,7,7,7], val = 7 Output: [] Every node matches, so the whole list is removed.
- The number of nodes in the list is in the range [0, 10^4]. - 1 <= Node.val <= 50 - 0 <= val <= 50
Removing a target value from a linked list looks trivial until the target sits at the front — where there is no previous node to re-route. This editorial builds the one trick that makes the head as ordinary as any other node.
next pointer; the list is its head pointer.next past it — no data is shifted.In plain words: walk the list and drop every node whose value is val, keeping the rest in order. Formally, return the head of the list containing exactly the nodes with Node.val != val, in their original sequence.
Worked example — head = [1,2,6,3,4,5,6], val = 6
remove every node whose value is 6
1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
x x (spliced out)
1 -> 2 -> 3 -> 4 -> 5
A ten-second question about guarantees separates someone who codes from someone who designs — it shows you found the edge cases before writing a single line.
“Can the list be empty?”
Yes, per the constraints. The answer must be an empty list, so the code cannot assume a first node exists.
“Can the matching nodes be consecutive, or sit at the head or tail?”
Yes to all — a run of matches at the front is the classic trap and drives the sentinel idea.
“Could every single node match the value?”
Yes, so the function must be able to return null, not just a shorter list.
“How long can the list be?”
Up to 10^4 nodes, so one linear pass is expected — no reason for anything worse than O(n).
Before I start, a couple of quick questions.
Can the list be empty, and can matching nodes appear at the head or in a consecutive run?
If so, I'll use a sentinel node before the head so the front needs no special case.
A node in the middle or end is easy to delete — its predecessor just re-points past it. The head is the sole exception: it has no predecessor to do the re-pointing.
... A -> B -> C ... delete B: A.next = C (easy) HEAD -> B -> C delete HEAD: who repoints? (nobody)
Place a sentinel dummy node whose next is the head. Now the real head does have a predecessor. One uniform loop handles the front and the interior identically, and you return dummy.next as the possibly-new head.
When you splice out prev.next, the new prev.next might also match (consecutive targets). So only move prev forward when you keep a node; after a deletion, re-check the same prev.
| Copy keepers | Sentinel splice | |
|---|---|---|
| Time | O(n) | O(n) |
| Space | O(n) | O(1) |
| Mutates input |
Both are linear in time; the sentinel splice wins by editing the list in place with no extra nodes. See the full code for each in the Approaches selector below.
Key takeaway
The sentinel (dummy head) node is the master key for linked-list problems: by giving the head a predecessor, it collapses "the front is a special case" into a single uniform loop. Splice while keeping prev fixed after each removal.
dummy -> head
prev = dummy
curr = head
while curr:
if curr.val == val: prev.next = curr.next # skip, keep prev
else: prev = curr # keep, advance prev
curr = curr.next
return dummy.next