Delete Nodes From Linked List Present in Array — Solution
Delete Nodes From Linked List Present in Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Delete Nodes From Linked List Present in Array is a medium coding problem on arrays and hash table, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array of distinct integers nums and the head of a linked list. Remove from the list every node whose value appears in nums, keeping the other nodes in their original order, and return the head of the modified list.
Example 1
Input: nums = [3,7], head = [7,1,3,9,7,4]
Output: [1,9,4]
Explanation: Both 7s and the 3 are removed.
Example 2
Input: nums = [2], head = [2,5,2,2]
Output: [5]
Explanation: Every 2 goes, including the head — the new head is the node holding 5.
Example 3
Input: nums = [8,6,4], head = [1,2,3]
Output: [1,2,3]
Explanation: No value of the list is in `nums`, so nothing changes.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^5All elements in nums are distinctThe number of nodes in the list is in the range [1, 10^5]1 <= Node.val <= 10^5At least one node of the list has a value not present in nums
Hints for Delete Nodes From Linked List Present in Array
Hint 1
Checking each node against the whole array costs
O(n * m); loadnumsinto a hash set first.Hint 2
Deleting the head is the awkward case. A dummy node in front of the head makes every node, the head included, have a predecessor.
Hint 3
Walk with
curstarting at the dummy: whilecur.nextis to be removed, skip it; otherwise advance. Returndummy.next.
How to solve Delete Nodes From Linked List Present in Array
Membership tests against a hash set are O(1), and a dummy node before the head turns head deletions into ordinary unlinking.
Approach
- Put every value of
numsinto a set. - Create
dummywithdummy.next = headand setcur = dummy. - While
cur.nextexists: if its value is in the set, unlink it (cur.next = cur.next.next) without moving; otherwise movecurforward. - Return
dummy.next.
Why it works
cur always points at a node that is kept (the dummy, or a node already checked), so each unlinking removes exactly the node examined and never skips one: after an unlink, cur.next is the next unexamined node.
Complexity
- Time —
O(n + m) - Space —
O(m)
Pitfalls
- Advancing
curafter an unlink skips the node that moved up, so two consecutive values to delete would leave the second. - Several leading nodes may need removing — the dummy handles them without special cases.
Reference solution
Python
from typing import List, Optional
def modifiedList(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.nextJava
public static ListNode modifiedList(int[] nums, ListNode head) {
HashSet<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;
}C++
ListNode* modifiedList(vector<int>& nums, ListNode* head) {
unordered_set<int> drop(nums.begin(), nums.end());
ListNode dummy(0, head);
ListNode* cur = &dummy;
while (cur->next) {
if (drop.count(cur->next->val)) cur->next = cur->next->next;
else cur = cur->next;
}
return dummy.next;
}JavaScript
var modifiedList = function(nums, head) {
var drop = new Set(nums);
var dummy = new ListNode(0, head), cur = dummy;
while (cur.next !== null) {
if (drop.has(cur.next.val)) cur.next = cur.next.next;
else cur = cur.next;
}
return dummy.next;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets