Dare2Solve
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:
Initialize Data Structures:
num_set
to store values from nums
for quick lookup.Traversal:
res
to simplify the construction of the resulting linked list.res_cur
to keep track of the current node in the result list.Iterate Through the Linked List:
head
):
num_set
, add it to res_cur
and update res_cur
.Return Result:
res.next
, which points to the head of the modified linked list, skipping the dummy node.nums
. Building the num_set
takes O(N) time, and iterating through the linked list takes O(M) time.nums
due to the space used by num_set
.class Solution {
public:
ListNode* modifiedList(vector<int>& nums, ListNode* head) {
ListNode* res = new ListNode();
ListNode* resCur = res;
ListNode* cur = head;
unordered_set<int> 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;
}
};
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
class Solution {
public ListNode modifiedList(int[] nums, ListNode head) {
ListNode res = new ListNode();
ListNode resCur = res;
ListNode cur = head;
Set<Integer> 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;
}
}
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;
};