Delete Nodes From Linked List Present in Array

medium linked list hash table set lookup

Problem

You are given an array of integers nums and the head of a linked list. Return the head of the modified list after removing every node whose value exists in nums. Because nums elements are unique, a hash set lets us test each node in O(1), so the whole list is cleaned in one pass.

Inputnums = [1,2,3], head = [1,2,3,4,5]

Output[4,5]

Nodes 1, 2, and 3 are in the set, so they are unlinked; 4 and 5 survive.

nums (comma-separated)

head (comma-separated)

def modifiedList(nums, head):
    to_delete = set(nums)               # O(1) membership tests
    dummy = ListNode(0, head)           # sentinel before head
    prev = dummy
    cur = head
    while cur:
        if cur.val in to_delete:
            prev.next = cur.next        # unlink the matching node
        else:
            prev = cur                  # keep node, advance prev
        cur = cur.next
    return dummy.next

function modifiedList(nums, head) {
  const toDelete = new Set(nums);          // O(1) membership tests
  const dummy = new ListNode(0, head);     // sentinel before head
  let prev = dummy;
  let cur = head;
  while (cur) {
    if (toDelete.has(cur.val)) {
      prev.next = cur.next;                // unlink the matching node
    } else {
      prev = cur;                          // keep node, advance prev
    }
    cur = cur.next;
  }
  return dummy.next;
}

ListNode modifiedList(int[] nums, ListNode head) {
    Set<Integer> toDelete = new HashSet<>();
    for (int n : nums) toDelete.add(n);      // O(1) membership tests
    ListNode dummy = new ListNode(0, head);  // sentinel before head
    ListNode prev = dummy, cur = head;
    while (cur != null) {
        if (toDelete.contains(cur.val)) {
            prev.next = cur.next;            // unlink the matching node
        } else {
            prev = cur;                      // keep node, advance prev
        }
        cur = cur.next;
    }
    return dummy.next;
}

ListNode* modifiedList(vector<int>& nums, ListNode* head) {
    unordered_set<int> toDelete(nums.begin(), nums.end());
    ListNode dummy(0, head);                 // sentinel before head
    ListNode* prev = &dummy;
    ListNode* cur = head;
    while (cur) {
        if (toDelete.count(cur->val)) {
            prev->next = cur->next;          // unlink the matching node
        } else {
            prev = cur;                      // keep node, advance prev
        }
        cur = cur->next;
    }
    return dummy.next;
}

Explanation

The task is a classic linked-list filter: delete any node whose value is one of the numbers in nums. The naive idea — for each node, scan the whole array — would be O(n · m). We can do far better.

First, pour nums into a hash set to_delete. Since the values are unique, the set holds them with no duplicates and answers "is this value marked for deletion?" in O(1) average time.

To delete cleanly we use a dummy / sentinel node placed in front of head. This removes the special case where the very first node (or a run of leading nodes) must be deleted — there is always a real prev pointer to rewire.

We walk the list with two pointers: cur visits each node, and prev trails the last kept node. If cur.val is in the set we splice it out with prev.next = cur.next, leaving prev where it is. Otherwise the node stays, so we advance prev = cur. Either way cur moves forward.

When the walk ends, dummy.next points at the head of the surviving list — which may differ from the original head if leading nodes were removed. Example: nums = [1], head = [1,2,1,2,1,2] deletes every 1 and returns [2,2,2].

Time: O(n + m) Space: O(m)