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 <= 105
1 <= nums[i] <= 105
All elements in nums are 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.
Solutions
Solution 1: Hash Table
We can use a hash table $\textit{s}$ to store all the elements in the array $\textit{nums}$. Then, we define a dummy node $\textit{dummy}$ and point it to the head node of the list $\textit{head}$.
Next, we traverse the list starting from the dummy node $\textit{dummy}$. If the value of the next node of the current node is in the hash table $\textit{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 $\textit{dummy}$.
The time complexity is $O(n + m)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$, and $m$ is the length of the list $\textit{head}$.
1 2 3 4 5 6 7 8 91011121314151617
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defmodifiedList(self,nums:List[int],head:Optional[ListNode])->Optional[ListNode]:s=set(nums)pre=dummy=ListNode(next=head)whilepre.next:ifpre.next.valins:pre.next=pre.next.nextelse:pre=pre.nextreturndummy.next
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcmodifiedList(nums[]int,head*ListNode)*ListNode{s:=map[int]bool{}for_,x:=rangenums{s[x]=true}dummy:=&ListNode{Next:head}forpre:=dummy;pre.Next!=nil;{ifs[pre.Next.Val]{pre.Next=pre.Next.Next}else{pre=pre.Next}}returndummy.Next}