3217. Delete Nodes From Linked List Present in Array

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

1. Initialize Data Structures: - Create a set num_set to store values from nums for quick lookup.
2. Traversal: - Initialize a dummy node res to simplify the construction of the resulting linked list. - Initialize res_cur to keep track of the current node in the result list.
3. Iterate Through the Linked List: - Traverse through the original linked list (head): - If the current node's value is not in num_set, add it to res_cur and update res_cur.
4. 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 the num_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 by num_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;
};