Remove Linked List Elements

The key idea

Removing a node means rerouting its predecessor's next past it. The head has no predecessor, so add a dummy node in front of it; then a single prev pointer can delete any matching node uniformly, including the original head.

Problem

You are given the head of a linked list and an integer val. Remove all the nodes of the linked list that have Node.val == val, and return the head of the new list.

Deleting a node means rerouting the link of its predecessor so the list skips over it. The matching node may be anywhere, including the very first node, so the original head itself can be removed. If every node matches, the result is an empty list (null).

Constraints

The number of nodes in the list is in the range [0, 10^4].
1 <= Node.val <= 50
0 <= val <= 50

Examples

Input: head = [1,2,6,3,4,5,6], val = 6 Output: [1,2,3,4,5]

Input: head = [], val = 1 Output: []

Input: head = [7,7,7,7], val = 7 Output: []

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →