🎨Now live: Try our Free AI Image Generation Feature

Intuition
To solve this problem, we can use a set to store all values from the nums
array for O(1) average-time complexity lookups. As we traverse through the linked list:
- If a node's value exists in the set, skip this node.
- Otherwise, add this node to the new linked list.
Approach
- Initialize Data Structures:
- Create a set
num_set
to store values fromnums
for quick lookup. - Traversal:
- Initialize a dummy node
res
to simplify the construction of the resulting linked list. - Initializeres_cur
to keep track of the current node in the result list. - Iterate Through the Linked List:
- Traverse through the original linked list (
head
): - If the current node's value is not innum_set
, add it tores_cur
and updateres_cur
. - Return Result:
- Return
res.next
, which points to the head of the modified linked list, skipping the dummy node.
Complexity
- Time Complexity: O(M + N), where M is the number of nodes in the linked list and N is the number of elements in
nums
. Building thenum_set
takes O(N) time, and iterating through the linked list takes O(M) time. - Space Complexity: O(N), where N is the number of elements in
nums
due to the space used bynum_set
.
Code
C++
class Solution {
public:
ListNode* modifiedList(vector& nums, ListNode* head) {
ListNode* res = new ListNode();
ListNode* resCur = res;
ListNode* cur = head;
unordered_set set(nums.begin(), nums.end());
while (cur) {
if (set.find(cur->val) == set.end()) {
resCur->next = new ListNode(cur->val);
resCur = resCur->next;
}
cur = cur->next;
}
return res->next;
}
};
Python
class Solution:
def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
res = ListNode()
res_cur = res
cur = head
num_set = set(nums)
while cur:
if cur.val not in num_set:
res_cur.next = ListNode(cur.val)
res_cur = res_cur.next
cur = cur.next
return res.next
Java
class Solution {
public ListNode modifiedList(int[] nums, ListNode head) {
ListNode res = new ListNode();
ListNode resCur = res;
ListNode cur = head;
Set set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
while (cur != null) {
if (!set.contains(cur.val)) {
resCur.next = new ListNode(cur.val);
resCur = resCur.next;
}
cur = cur.next;
}
return res.next;
}
}
JavaScript
var modifiedList = function (nums, head) {
var res = new ListNode();
var resCur = res;
var cur = head;
var set = new Set(nums);
while (cur) {
if (!set.has(cur.val)) {
resCur.next = new ListNode(cur.val);
resCur = resCur.next;
}
cur = cur.next;
}
return res.next;
};