Watch 10 video solutions for Delete Nodes From Linked List Present in Array, a medium level problem involving Array, Hash Table, Linked List. This walkthrough by codestorywithMIK has 9,556 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of integers nums and the head of a linked list. Return the head of the modified linked list after removing all nodes from the linked list that have a value that exists in nums.
Example 1:
Input: nums = [1,2,3], head = [1,2,3,4,5]
Output: [4,5]
Explanation:
Remove the nodes with values 1, 2, and 3.
Example 2:
Input: nums = [1], head = [1,2,1,2,1,2]
Output: [2,2,2]
Explanation:
Remove the nodes with value 1.
Example 3:
Input: nums = [5], head = [1,2,3,4]
Output: [1,2,3,4]
Explanation:
No node has value 5.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105nums are unique.[1, 105].1 <= Node.val <= 105nums.Problem Overview: You receive an integer array and the head of a linked list. Any node whose value exists in the array must be removed from the list. The result should be the filtered linked list that keeps only values not present in the array.
Approach 1: Set-Based Filtering of Linked List (Time: O(n + m), Space: O(m))
The most practical solution converts the array into a hash set for constant-time membership checks. Insert every value from the array into the set, then iterate through the linked list. For each node, check whether node.val exists in the set. If it does, bypass the node by updating the previous node's next pointer. If not, keep the node and continue traversing.
This approach works well because hash table lookups run in average O(1) time. Building the set takes O(m) where m is the array size, and scanning the linked list takes O(n). The total time complexity becomes O(n + m) with O(m) extra space. This is the cleanest and most scalable solution when the array can be large.
Approach 2: Two-Pointer Technique Without Extra Space (Time: O(n * m), Space: O(1))
If extra memory is restricted, you can avoid a hash set and instead check each node directly against the array. Traverse the linked list with two pointers: prev and curr. For every node, scan the entire array to determine whether the value should be removed. If the value appears in the array, update prev.next to skip the current node. Otherwise, move both pointers forward.
This technique uses constant auxiliary space since no additional data structures are created. The downside is performance. Each linked list node may require scanning the entire array, resulting in O(n * m) time. It works only when the array is small or memory constraints are strict.
Recommended for interviews: The hash set filtering approach is what most interviewers expect. It demonstrates that you recognize when to trade a small amount of memory for a large performance gain. The two-pointer approach without extra space is still useful to discuss because it shows awareness of memory constraints and algorithmic trade-offs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set-Based Filtering of Linked List | O(n + m) | O(m) | General case. Fast lookups using a hash set make it the optimal and most scalable approach. |
| Two-Pointer Technique Without Extra Space | O(n * m) | O(1) | Useful when memory usage must stay minimal or when the array size is very small. |