LeetCode #203 Easy

Remove Linked List Elements

Remove every node whose value equals a given target.

linked-listtwo-pointers
Open on LeetCode ↗
02

Intuition

💡

The case that breaks the obvious solution is the one people test last: what if the HEAD is the value you have to remove? Every other node can be unlinked by its predecessor, but the head has none, so you end up writing one branch for the head and another for everything else - and then the head-removal branch has to loop too, because the second node might match as well. A dummy node placed in front of the head deletes that whole special case: now every real node has a predecessor and one loop covers all of them. The second trap is advancing the pointer after a deletion. When you unlink a node, the next one slides into its place and needs the SAME predecessor, so prev must stay put and only move when you keep a node. Return dummy.next rather than head, since head may be one of the nodes you removed.

03

Approach

1

Put a dummy in front

Create a node whose next is the head. Its only job is to give the real head a predecessor so that removing the head is not a special case. This costs one node and removes an entire branch of logic, which is almost always the right trade in linked-list problems.

2

Walk with a trailing pointer

Keep cur at the node before the one you are judging. If cur.next matches the target, set cur.next = cur.next.next to splice it out, and crucially do NOT advance cur - the node that just slid into that position has not been checked yet and shares the same predecessor. Only when you keep a node does cur move forward.

3

Return the dummy's next

The original head may itself have been removed, so returning it would hand back a deleted node or a stale chain. dummy.next always points at whatever the real head is now, including None when every node matched. One pass, O(1) extra space.

04

Solution & live demo

python
1class Solution:
2 def removeElements(self, head, val):
3 dummy = ListNode(0)
4 dummy.next = head
5 cur = dummy
6 while cur.next:
7 if cur.next.val == val:
8 cur.next = cur.next.next
9 else:
10 cur = cur.next
11 return dummy.next
05

Edge cases

Head matches the target

The dummy handles it with no special branch.

Every node matches

dummy.next ends as None, which is the correct empty list.

Consecutive matches

prev stays put after a deletion, so runs collapse correctly.

Empty list

The loop never runs and dummy.next is None.

06

Complexity

Time
O(n)
Space
O(1)
One pass. The dummy node is the only extra allocation.