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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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).
| 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. |
Remove Nodes From Linked List - Leetcode 2487 - Python • NeetCodeIO • 13,302 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