Delete Nodes From Linked List Present in Array

Medium
2027.

Delete Nodes From Linked List Present in Array

Delete Nodes From Linked List Present in Array is a medium coding problem on arrays and hash table, asked in Amazon and Google interviews.

You are given an array of distinct integers nums and the head of a linked list. Remove from the list every node whose value appears in nums, keeping the other nodes in their original order, and return the head of the modified list.

Example 1

Input
nums = [3,7], head = [7,1,3,9,7,4]
Output
[1,9,4]
Explanation
Both 7s and the 3 are removed.

Example 2

Input
nums = [2], head = [2,5,2,2]
Output
[5]
Explanation
Every 2 goes, including the head — the new head is the node holding 5.

Example 3

Input
nums = [8,6,4], head = [1,2,3]
Output
[1,2,3]
Explanation
No value of the list is in `nums`, so nothing changes.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • All elements in nums are distinct
  • The number of nodes in the list is in the range [1, 10^5]
  • 1 <= Node.val <= 10^5
  • At least one node of the list has a value not present in nums
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * 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) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Delete Nodes From Linked List Present in Array — Solution

Delete Nodes From Linked List Present in Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Delete Nodes From Linked List Present in Array is a medium coding problem on arrays and hash table, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array of distinct integers nums and the head of a linked list. Remove from the list every node whose value appears in nums, keeping the other nodes in their original order, and return the head of the modified list.

Example 1

Input: nums = [3,7], head = [7,1,3,9,7,4]
Output: [1,9,4]
Explanation: Both 7s and the 3 are removed.

Example 2

Input: nums = [2], head = [2,5,2,2]
Output: [5]
Explanation: Every 2 goes, including the head — the new head is the node holding 5.

Example 3

Input: nums = [8,6,4], head = [1,2,3]
Output: [1,2,3]
Explanation: No value of the list is in `nums`, so nothing changes.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5
  • All elements in nums are distinct
  • The number of nodes in the list is in the range [1, 10^5]
  • 1 <= Node.val <= 10^5
  • At least one node of the list has a value not present in nums

Hints for Delete Nodes From Linked List Present in Array

  1. Hint 1

    Checking each node against the whole array costs O(n * m); load nums into a hash set first.

  2. Hint 2

    Deleting the head is the awkward case. A dummy node in front of the head makes every node, the head included, have a predecessor.

  3. Hint 3

    Walk with cur starting at the dummy: while cur.next is to be removed, skip it; otherwise advance. Return dummy.next.

How to solve Delete Nodes From Linked List Present in Array

Membership tests against a hash set are O(1), and a dummy node before the head turns head deletions into ordinary unlinking.

Approach

  1. Put every value of nums into a set.
  2. Create dummy with dummy.next = head and set cur = dummy.
  3. While cur.next exists: if its value is in the set, unlink it (cur.next = cur.next.next) without moving; otherwise move cur forward.
  4. Return dummy.next.

Why it works

cur always points at a node that is kept (the dummy, or a node already checked), so each unlinking removes exactly the node examined and never skips one: after an unlink, cur.next is the next unexamined node.

Complexity

  • Time — O(n + m)
  • Space — O(m)

Pitfalls

  • Advancing cur after an unlink skips the node that moved up, so two consecutive values to delete would leave the second.
  • Several leading nodes may need removing — the dummy handles them without special cases.

Reference solution

Python

from typing import List, Optional

def modifiedList(nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
    drop = set(nums)
    dummy = ListNode(0, head)
    cur = dummy
    while cur.next:
        if cur.next.val in drop:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return dummy.next

Java

public static ListNode modifiedList(int[] nums, ListNode head) {
    HashSet<Integer> drop = new HashSet<>();
    for (int x : nums) drop.add(x);
    ListNode dummy = new ListNode(0, head), cur = dummy;
    while (cur.next != null) {
        if (drop.contains(cur.next.val)) cur.next = cur.next.next;
        else cur = cur.next;
    }
    return dummy.next;
}

C++

ListNode* modifiedList(vector<int>& nums, ListNode* head) {
    unordered_set<int> drop(nums.begin(), nums.end());
    ListNode dummy(0, head);
    ListNode* cur = &dummy;
    while (cur->next) {
        if (drop.count(cur->next->val)) cur->next = cur->next->next;
        else cur = cur->next;
    }
    return dummy.next;
}

JavaScript

var modifiedList = function(nums, head) {
    var drop = new Set(nums);
    var dummy = new ListNode(0, head), cur = dummy;
    while (cur.next !== null) {
        if (drop.has(cur.next.val)) cur.next = cur.next.next;
        else cur = cur.next;
    }
    return dummy.next;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets