Drop Matching Nodes
EasyLinked List
Problem
An order queue is a singly linked list of product ids. A product has been recalled and every order for it must disappear.
Given the head and an integer target, remove every node whose value equals target and return the new head.
Example 1
- Input:
- head = [3, 8, 3, 5, 3], target = 3
- Output:
- [8, 5]
All three nodes with value 3 are removed, including the head.
Example 2
- Input:
- head = [6, 6], target = 6
- Output:
- []
Example 3
- Input:
- head = [1, 2], target = 9
- Output:
- [1, 2]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- 1 ≤ node.val, target ≤ 50
Hint
Show the first hint
Removing a node means changing its predecessor's next pointer. Which node has no predecessor?
Walkthrough
How to approach it
01Clarify before coding
- Can the head itself match? Yes, and so can a whole run of leading nodes.
- Can every node match? Yes: return an empty list.
- Should the remaining order be kept? Yes, unchanged.
02Brute force
Build a brand-new list by copying every non-matching value.
Cost: O(n) time but O(n) extra space for the new nodes; the in-place version needs O(1).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.