Delete Nodes From Linked List Present in Array
MedPrompt
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] <= 105- All elements in
numsare unique. - The number of nodes in the given list is in the range
[1, 105]. 1 <= Node.val <= 105- The input is generated such that there is at least one node in the linked list that has a value not present in
nums.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through each node of the linked list and, for each node, scanning the entire nums array to check if the node's value should be deleted. It is the most straightforward but least efficient method.
Algorithm
- Create a dummy node and point its
nextto theheadof the list. This simplifies handling cases where the head node itself needs to be deleted. - Initialize two pointers,
prev = dummyandcurrent = head. - Traverse the list using the
currentpointer until it becomesnull. - For each
currentnode, iterate through the entirenumsarray. - If
current.valis found innums, set a flagtoDelete = trueand break the inner loop. - After the inner loop, if
toDeleteis true, bypass thecurrentnode by settingprev.next = current.next. Theprevpointer does not move. - If
toDeleteis false, it means the node should be kept. Advance theprevpointer:prev = current. - In every iteration of the outer loop, advance the
currentpointer to the next node:current = current.next. - After the loop finishes, return
dummy.next, which points to the head of the modified list.
Walkthrough
The brute-force method directly translates the problem statement into code. We traverse the linked list from head to tail. For each node we encounter, we perform a second traversal, this time through the nums array, to check if the node's value exists in the array.
To facilitate the deletion of nodes, including the head node, we use a dummy node. The dummy node's next pointer is set to the original head. We then use two pointers, prev and current, to iterate through the list. prev always points to the last node that was kept, and current points to the node being inspected.
If current.val is found in nums, we remove the current node by linking prev to current.next. If current.val is not in nums, we keep the node by advancing prev to current. The current pointer is always advanced to the next node in the list in each step.
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode modifiedList(int[] nums, ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; ListNode current = head; while (current != null) { boolean toDelete = false; for (int num : nums) { if (current.val == num) { toDelete = true; break; } } if (toDelete) { // Delete current node by skipping it prev.next = current.next; } else { // Keep current node, so move prev forward prev = current; } // Move to the next node for the next iteration current = current.next; } return dummy.next; }}Complexity
Time
O(N * M), where N is the number of nodes in the linked list and M is the number of elements in the `nums` array. For each of the N nodes, we perform a linear scan of the M elements in `nums`.
Space
O(1). We only use a few extra pointers (`dummy`, `prev`, `current`) regardless of the input size.
Trade-offs
Pros
Simple to understand and implement.
Constant space complexity, as it doesn't use any auxiliary data structures that scale with input size.
Cons
Highly inefficient with a time complexity of O(N * M), where N is the number of nodes and M is the length of the
numsarray.Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with large test cases.
This approach significantly improves performance by first storing all values from the nums array into a HashSet. This allows for checking if a node's value needs to be deleted in constant average time, reducing the overall time complexity from quadratic to linear.
Algorithm
- Create a
HashSetof integers. - Iterate through the
numsarray and add each element to theHashSet. This takes O(M) time. - Create a dummy node and point its
nextto theheadof the list. - Initialize two pointers,
prev = dummyandcurrent = head. - Traverse the list using the
currentpointer until it becomesnull. - For each
currentnode, check if its value is present in theHashSetusingset.contains(current.val). This is an O(1) average time operation. - If the value is in the set, bypass the
currentnode by settingprev.next = current.next. - Otherwise, the node is kept, so we advance the
prevpointer:prev = current. - In every iteration, advance the
currentpointer:current = current.next. - Return
dummy.next.
Walkthrough
To optimize the process, we can eliminate the costly repeated searches in the nums array. The key idea is to use a data structure that provides near-constant time lookups. A HashSet is a perfect choice for this.
First, we iterate through the nums array and store all its elements in a HashSet. This pre-processing step allows us to later check for the existence of a value in O(1) average time.
After building the set, we traverse the linked list using the same dummy node and prev/current pointer technique as in the brute-force approach. However, for each current node, instead of looping through nums, we simply perform a set.contains(current.val) check.
If the value is in the set, we delete the node (prev.next = current.next). Otherwise, we keep it and advance prev (prev = current). This reduces the time complexity from quadratic to linear, making it an efficient solution.
import java.util.HashSet;import java.util.Set; /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public ListNode modifiedList(int[] nums, ListNode head) { // Step 1: Create a HashSet for O(1) average time lookups. Set<Integer> numsSet = new HashSet<>(); for (int num : nums) { numsSet.add(num); } // Step 2: Use a dummy node to simplify head deletion. ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; ListNode current = head; // Step 3: Traverse the linked list. while (current != null) { // Step 4: Check if the current node's value is in the set. if (numsSet.contains(current.val)) { // If yes, bypass the current node. prev.next = current.next; } else { // If no, this node is kept. Move prev to current. prev = current; } // Move to the next node in the original list. current = current.next; } // The modified list starts at dummy.next. return dummy.next; }}Complexity
Time
O(N + M), where N is the number of nodes and M is the length of `nums`. It takes O(M) to build the HashSet and O(N) to traverse the linked list, with each node check being O(1) on average.
Space
O(M). The space is dominated by the HashSet used to store the M elements from the `nums` array.
Trade-offs
Pros
Highly efficient with a linear time complexity of O(N + M).
This is the optimal approach for the given constraints and passes all test cases efficiently.
Cons
Requires extra space of O(M) to store the elements of
numsin a HashSet.
Solutions
Solution
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode modifiedList ( int [] nums , ListNode head ) { Set < Integer > s = new HashSet <>(); for ( int x : nums ) { s . add ( x ); } ListNode dummy = new ListNode ( 0 , head ); for ( ListNode pre = dummy ; pre . next != null ;) { if ( s . contains ( pre . next . val )) { pre . next = pre . next . next ; } else { pre = pre . next ; } } return dummy . next ; } }/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * modifiedList ( vector < int >& nums , ListNode * head ) { unordered_set < int > s ( nums . begin (), nums . end ()); ListNode * dummy = new ListNode ( 0 , head ); for ( ListNode * pre = dummy ; pre -> next ;) { if ( s . count ( pre -> next -> val )) { pre -> next = pre -> next -> next ; } else { pre = pre -> next ; } } return dummy -> next ; } };# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def modifiedList ( self , nums : List [ int ], head : Optional [ ListNode ] ) -> Optional [ ListNode ]: s = set ( nums ) pre = dummy = ListNode ( next = head ) while pre . next : if pre . next . val in s : pre . next = pre . next . next else : pre = pre . next return dummy . nextVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.