LeetCode 3217. Delete Nodes From Linked List Present in Array — JavaScript

Qualcomm CEO Cristiano Amon says the company is working with Samsung and Google on a mixed-reality set of smart glasses linked to a smartphone

Intuition

The problem involves removing elements from a linked list based on a given array of values. The first thought is to iterate through the linked list and remove nodes whose values exist in the array. Using a set for the array allows for O(1) lookups, making the process efficient.

Approach

1. Use a Set: Convert the array nums into a set, numsSet, to allow for quick lookup of elements.
2. Dummy Node: Initialize a dummy node that helps in easily handling edge cases such as when the head needs to be removed.
3. Traversal and Filtering: Traverse the linked list. For each node, check if its value exists in numsSet. If it does not exist, link it to the new list. If it does exist, skip it.
4. Terminate the List: Ensure that the last node of the new list points to null to avoid any unwanted connections.
5. Return the Result: Return the list starting from the next node of the dummy node.

Complexity

• Time complexity:
  O(n + m) where n is the number of nodes in the linked list, and m is the length of the nums array. Creating the set takes O(m), and traversing the list takes O(n).
• Space complexity:
  O(m) for storing the nums array in a set. The space used for the new linked list is still O(n), but we are reusing the existing nodes, so no extra space is required beyond the set.

Code

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {number[]} nums
 * @param {ListNode} head
 * @return {ListNode}
 */
var modifiedList = function(nums, head) {
    let dummyNode = new ListNode(null);  // Placeholder node
    let current = dummyNode;  // Pointer for the new list
    const numsSet = new Set(nums);  // Set for quick lookup
    
    while (head) {
        if (!numsSet.has(head.val)) {  // If the value is not in nums
            current.next = head;  // Add the node to the new list
            current = current.next;  // Move the pointer forward
        }
        head = head.next;  // Move to the next node in the original list
    }
    
    current.next = null;  // Terminate the new list
    
    return dummyNode.next;  // Return the new list, starting from the next node of dummyNode
};

Join me and over 40 million users who love Revolut. Sign up with my link below: https://revolut.com/referral/?referral-code=weijhih!AUG2-24-VR-IE-AE