Delete Nodes From Linked List Present in Array
Delete Nodes From Linked List Present in Array is a medium linked list problem solved with the dummy node pattern pattern.
The best approach, optimal (hash set + dummy node), runs in O(n + m) time and O(m) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan nums per node) up.
Problem
Given an array of values nums and the head of a linked list, remove every node whose value appears in nums and return the new head.
Examples
Example 1
- Input
nums = [2, 5], head = [2, 3, 5, 4, 2]- Output
[3, 4]
Example 2
- Input
nums = [9], head = [1, 9, 9]- Output
[1]
Constraints
1 <= nums.length <= 10^5, values distinct- The list has
1to10^5nodes; at least one node is not in nums.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan nums per node) | O(n · m) | O(1) |
| Optimal (hash set + dummy node) | O(n + m) | O(m) |
1Brute force (scan nums per node)
O(n · m)O(1)For each node, loop through nums to see if its value should be removed.
- Dummy node; for each next node, linear search nums.
class Solution {
public ListNode modifiedList(int[] nums, ListNode head) {
ListNode dummy = new ListNode(0, head), cur = dummy;
while (cur.next != null) {
boolean remove = false;
for (int x : nums) if (x == cur.next.val) { remove = true; break; }
if (remove) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}
}class Solution:
def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0, head)
cur = dummy
while cur.next:
remove = False
for x in nums:
if x == cur.next.val:
remove = True
break
if remove:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.nextclass Solution {
public:
ListNode* modifiedList(vector<int>& nums, ListNode* head) {
ListNode* dummy = new ListNode(0, head);
ListNode* cur = dummy;
while (cur->next != nullptr) {
bool remove = false;
for (int x : nums) if (x == cur->next->val) { remove = true; break; }
if (remove) cur->next = cur->next->next;
else cur = cur->next;
}
return dummy->next;
}
};function modifiedList(nums, head) {
const dummy = new ListNode(0, head);
let cur = dummy;
while (cur.next !== null) {
let remove = false;
for (const x of nums) if (x === cur.next.val) { remove = true; break; }
if (remove) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}2Optimal (hash set + dummy node)
O(n + m)O(m)Put nums in a set, then remove nodes as in Remove Linked List Elements, using a dummy node for the head.
- Build a set (or boolean array, since values are small) from nums.
- Walk with a dummy node and unlink nodes whose value is in the set.
class Solution {
public ListNode modifiedList(int[] nums, ListNode head) {
Set<Integer> drop = new HashSet<>();
for (int x : nums) drop.add(x);
ListNode dummy = new ListNode(0, head), cur = dummy;
while (cur.next != null) {
if (drop.contains(cur.next.val)) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}
}class Solution:
def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
drop = set(nums)
dummy = ListNode(0, head)
cur = dummy
while cur.next:
if cur.next.val in drop:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.nextclass Solution {
public:
ListNode* modifiedList(vector<int>& nums, ListNode* head) {
unordered_set<int> drop(nums.begin(), nums.end());
ListNode* dummy = new ListNode(0, head);
ListNode* cur = dummy;
while (cur->next != nullptr) {
if (drop.count(cur->next->val)) cur->next = cur->next->next;
else cur = cur->next;
}
return dummy->next;
}
};function modifiedList(nums, head) {
const drop = new Set(nums);
const dummy = new ListNode(0, head);
let cur = dummy;
while (cur.next !== null) {
if (drop.has(cur.next.val)) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
}Edge cases to test
- Head node is removed
- Long runs of removed nodes
Hints
Hint 1
Checking membership in an array each time is slow. What structure answers contains in O(1)?
FAQ
What is the best time complexity for Delete Nodes From Linked List Present in Array?
Optimal (hash set + dummy node) runs in O(n + m) time and O(m) extra space.
Which pattern does Delete Nodes From Linked List Present in Array use?
It is a linked list problem that uses the dummy node pattern pattern. Other problems with the same pattern: Remove Linked List Elements, Merge Two Sorted Lists, Rotate List.
Is there a brute force solution for Delete Nodes From Linked List Present in Array?
Yes. Brute force (scan nums per node) takes O(n · m) time and O(1) space. For each node, loop through nums to see if its value should be removed.
Which edge cases should I test for Delete Nodes From Linked List Present in Array?
Head node is removed; Long runs of removed nodes.