POTD-Leet Code 3217 (Delete Nodes From Linked List Present in Array) in JS

To solve “Delete Nodes From Linked List Present in Array” (problem 3217), the goal is to remove all nodes from a linked list that have values present in a given array. Below is the approach and the JavaScript solution.

Problem Overview:

• You are given a singly linked list and an array of values.
• You need to remove all nodes from the linked list that have values present in the array.

Approach:

1. Set for Fast Lookups:

• Since we need to check if a value exists in the array, converting the array into a Set allows for fast lookup in O(1) time for each node.

1. Traversing the Linked List:

• Traverse the linked list and, for each node, check if its value is present in the Set. If it is, you remove that node by adjusting the pointers.

1. Edge Cases:

• Handle cases where the head of the linked list needs to be deleted.
• Handle cases where the array is empty (in this case, no nodes are deleted).

JavaScript Code:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val);
 *     this.next = (next===undefined ? null : next);
 * }
/**
 * @param {ListNode} head
 * @param {number[]} nums
 * @return {ListNode}
 */
var deleteNodes = function(head, nums) {
    // Convert the array to a Set for fast lookup
    let numsSet = new Set(nums);

    // Create a dummy node to simplify edge case handling (removing the head)
    let dummy = new ListNode(0);
    dummy.next = head;

    // Initialize pointers
    let prev = dummy;
    let current = head;

    // Traverse the linked list
    while (current !== null) {
        if (numsSet.has(current.val)) {
            // Delete the current node by adjusting the prev pointer
            prev.next = current.next;
        } else {
            // Move the prev pointer if no deletion
            prev = current;
        }
        // Move the current pointer to the next node
        current = current.next;
    }

    // Return the updated list
    return dummy.next;
};

// Example usage:
// Linked List: 1 -> 2 -> 3 -> 4
// nums = [2, 3]
// After deletion, the list should be: 1 -> 4

Explanation:

1. Set Conversion:

• The given array nums is converted into a Set to allow for O(1) lookups when checking if a node’s value should be deleted.

1. Dummy Node:

• A dummy node is used to handle edge cases where the head of the linked list might need to be removed. This dummy node simplifies the code by ensuring that we always have a node (prev) that points to the current node being evaluated.

1. Traversal and Deletion:

• The linked list is traversed using two pointers, prev and current. If the current node’s value is found in the Set, it is deleted by skipping it (i.e., adjusting prev.next to current.next).
• If the node is not in the set, we simply move prev forward.

1. Returning the Result:

• The result is returned as dummy.next because dummy was pointing to the original head.

How does the code work without defining ListNode?

If you’re working in a coding environment where the ListNode class is already provided or assumed, such as in LeetCode, the platform automatically provides the definition for ListNode as part of the problem’s setup. In competitive programming or interviews, problems involving linked lists usually assume that this basic node structure is available and predefined.

Time Complexity:

• O(n + m) where:
• n is the length of the linked list.
• m is the size of the input array nums.
• Converting the array to a Set takes O(m), and traversing the linked list takes O(n).

Space Complexity:

• O(m): The space complexity is determined by the space used to store the Set, which contains up to m elements.