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.
This approach uses a set for fast lookup of values that need to be removed from the linked list. By iterating through the linked list and checking if each node's value is in the set, we can efficiently determine which nodes to skip and which to keep.
The solution initializes a boolean array lookup to quickly check if a node value should be removed. As we traverse the list, we either skip or keep nodes based on the contents of lookup. A dummy node simplifies edge cases, like removing the list's head.
Time Complexity: O(N + M), where N is the length of the linked list and M is the size of nums.
Space Complexity: O(M), where M is the size of nums.
This approach leverages a two-pointer technique where the result is constructed in-place. Although it doesn't require extra storage for the set, it does involve modifications that make subsequent operations more complex in favor of reducing space usage.
The C solution avoids extra space by implementing a linear search function isInArray that checks for value presence within the nums array, although less efficient than using a set for larger inputs.
Time Complexity: O(N * M), where N is the length of the linked list and M is the size of nums.
Space Complexity: O(1).
We can use a hash table s to store all the elements in the array nums. Then, we define a dummy node dummy and point it to the head node of the list head.
Next, we traverse the list starting from the dummy node dummy. If the value of the next node of the current node is in the hash table s, we make the current node point to the next next node; otherwise, we move the current node pointer to the next node.
Finally, we return the next node of the dummy node dummy.
The time complexity is O(n + m), and the space complexity is O(n). Here, n is the length of the array nums, and m is the length of the list head.
| Approach | Complexity |
|---|---|
| Set-Based Filtering of Linked List | Time Complexity: O(N + M), where N is the length of the linked list and M is the size of nums. |
| Two-Pointer Technique Without Extra Space | Time Complexity: O(N * M), where N is the length of the linked list and M is the size of nums. |
| Hash Table | — |
| 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. |
Delete Nodes From Linked List Present in Array | Simple | Dry Run | Leetcode 3217 | codestorywithMIK • codestorywithMIK • 9,556 views views
Watch 9 more video solutions →Practice Delete Nodes From Linked List Present in Array with our built-in code editor and test cases.
Practice on FleetCode