Start practising

Delete Nodes From Linked List Present in Array

Medium Linked List Dummy Node Pattern Original on LeetCode

Delete Nodes From Linked List Present in Array is a medium linked list problem solved with the dummy node pattern pattern. The best approach, optimal (hash set + dummy node), runs in O(n + m) time and O(m) space. Below are 2 approaches in Java, from brute force (scan nums per node) up.

Problem

Given an array of values nums and the head of a linked list, remove every node whose value appears in nums and return the new head.

Examples

Example 1

Input
nums = [2, 5], head = [2, 3, 5, 4, 2]
Output
[3, 4]

Example 2

Input
nums = [9], head = [1, 9, 9]
Output
[1]

Constraints

  • 1 <= nums.length <= 10^5, values distinct
  • The list has 1 to 10^5 nodes; at least one node is not in nums.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Brute force (scan nums per node)O(n · m)O(1)
Optimal (hash set + dummy node)O(n + m)O(m)

1Brute force (scan nums per node)

TimeO(n · m)
SpaceO(1)

For each node, loop through nums to see if its value should be removed.

  1. Dummy node; for each next node, linear search nums.
Java
class Solution {
    public ListNode modifiedList(int[] nums, ListNode head) {
        ListNode dummy = new ListNode(0, head), cur = dummy;
        while (cur.next != null) {
            boolean remove = false;
            for (int x : nums) if (x == cur.next.val) { remove = true; break; }
            if (remove) cur.next = cur.next.next;
            else cur = cur.next;
        }
        return dummy.next;
    }
}

2Optimal (hash set + dummy node)

TimeO(n + m)
SpaceO(m)

Put nums in a set, then remove nodes as in Remove Linked List Elements, using a dummy node for the head.

  1. Build a set (or boolean array, since values are small) from nums.
  2. Walk with a dummy node and unlink nodes whose value is in the set.
Java
class Solution {
    public ListNode modifiedList(int[] nums, ListNode head) {
        Set<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;
    }
}

Edge cases to test

  • Head node is removed
  • Long runs of removed nodes

Hints

Hint 1

Checking membership in an array each time is slow. What structure answers contains in O(1)?

FAQ

What is the best time complexity for Delete Nodes From Linked List Present in Array?

Optimal (hash set + dummy node) runs in O(n + m) time and O(m) extra space.

Which pattern does Delete Nodes From Linked List Present in Array use?

It is a linked list problem that uses the dummy node pattern pattern. Other problems with the same pattern: Remove Linked List Elements, Merge Two Sorted Lists, Rotate List.

Is there a brute force solution for Delete Nodes From Linked List Present in Array?

Yes. Brute force (scan nums per node) takes O(n · m) time and O(1) space. For each node, loop through nums to see if its value should be removed.

Which edge cases should I test for Delete Nodes From Linked List Present in Array?

Head node is removed; Long runs of removed nodes.