Problem Description

You have a linked list and an array of integers called nums. Your task is to remove all nodes from the linked list whose values appear in the nums array, then return the modified linked list.

For example, if you have a linked list with values 1 -> 2 -> 3 -> 4 -> 5 and nums = [2, 4], you need to remove the nodes with values 2 and 4. The resulting linked list would be 1 -> 3 -> 5.

The solution uses a hash set to store all values from nums for quick lookup. It creates a dummy node that points to the original head of the linked list. This dummy node helps handle edge cases where the head itself needs to be removed.

The algorithm traverses the linked list using a pointer pre starting from the dummy node. At each step, it checks if the next node's value exists in the hash set s. If it does, the algorithm "skips" that node by updating pre.next to point to pre.next.next, effectively removing the node from the list. If the value doesn't exist in the set, the pointer moves forward normally to the next node.

After processing all nodes, the function returns dummy.next, which points to the new head of the modified linked list. The time complexity is O(n + m) where n is the length of the linked list and m is the length of the nums array, while the space complexity is O(m) for storing the hash set.

Intuition

When we need to remove nodes from a linked list based on certain values, the main challenge is handling the connections properly. If we remove a node, we need to make sure the previous node points to the next node after the removed one, maintaining the chain.

The first insight is that checking if a value exists in the nums array repeatedly would be inefficient. If we check each node's value against every element in nums, we'd have O(n * m) time complexity. Converting nums to a hash set gives us O(1) lookup time, significantly improving efficiency.

The second key insight is using a dummy node. Why? Consider if we need to remove the first node (head) of the list. Without a dummy node, we'd need special logic to handle this case - we'd have to update the head reference itself. With a dummy node pointing to the head, removing the first node becomes just like removing any other node: we update dummy.next to skip it.

The traversal strategy comes naturally: we maintain a pointer to the node before the one we're examining. This way, when we find a node to remove, we already have access to the previous node and can update its next pointer to skip the unwanted node. We call this pointer pre (for previous).

As we traverse, we check pre.next.val (the value of the node we're examining). If it's in our set, we bypass it by setting pre.next = pre.next.next. If not, we move our pre pointer forward. This approach ensures we never lose track of the list structure while removing nodes.

Learn more about Linked List patterns.

Solution Approach

Following the hash table approach, we implement the solution in these steps:

Step 1: Create a Hash Set

s = set(nums)

We convert the nums array into a set s for O(1) lookup time. This allows us to quickly check if a node's value should be removed.

Step 2: Set Up Dummy Node

pre = dummy = ListNode(next=head)

We create a dummy node and point it to the original head. The variable pre will traverse the list, while dummy stays at the beginning to help us return the modified list's head later.

Step 3: Traverse and Remove Nodes

while pre.next:
    if pre.next.val in s:
        pre.next = pre.next.next
    else:
        pre = pre.next

We iterate through the list using pre.next as our condition. This ensures we always have access to the node before the one we're examining.

• If pre.next.val is in the set s, we need to remove this node. We do this by updating pre.next to point to pre.next.next, effectively skipping the current node and removing it from the list.
• If the value is not in the set, we simply move forward by updating pre = pre.next.

Notice that when we remove a node, we don't move pre forward. This is important because after removal, pre.next now points to a new node that we haven't checked yet.

Step 4: Return the Modified List

return dummy.next

Since dummy still points to the position before the original head, dummy.next gives us the head of the modified list. This works even if the original head was removed.

The algorithm processes each node exactly once, giving us O(n) time complexity for traversal, plus O(m) for creating the set, resulting in overall O(n + m) time complexity.

Example Walkthrough

Let's walk through a concrete example to see how the algorithm works step by step.

Given:

• Linked list: 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
• nums = [6, 2]
• Goal: Remove all nodes with values 6 and 2

Step 1: Create Hash Set

s = {6, 2}

Step 2: Initialize Dummy Node

dummy -> 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
  ↑
 pre

We create a dummy node pointing to head (1), and pre starts at dummy.

Step 3: Traverse and Remove

Iteration 1:

• Check pre.next.val = 1
• Is 1 in set {6, 2}? No
• Move pre forward

dummy -> 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
         ↑
        pre

Iteration 2:

• Check pre.next.val = 2
• Is 2 in set {6, 2}? Yes
• Skip node 2: pre.next = pre.next.next

dummy -> 1 -----> 6 -> 3 -> 4 -> 5 -> 6
         ↑
        pre

Note: pre stays at node 1

Iteration 3:

• Check pre.next.val = 6
• Is 6 in set {6, 2}? Yes
• Skip node 6: pre.next = pre.next.next

dummy -> 1 ----------> 3 -> 4 -> 5 -> 6
         ↑
        pre

Note: pre still stays at node 1

Iteration 4:

• Check pre.next.val = 3
• Is 3 in set {6, 2}? No
• Move pre forward

dummy -> 1 -> 3 -> 4 -> 5 -> 6
              ↑
             pre

Iteration 5:

• Check pre.next.val = 4
• Is 4 in set {6, 2}? No
• Move pre forward

dummy -> 1 -> 3 -> 4 -> 5 -> 6
                   ↑
                  pre

Iteration 6:

• Check pre.next.val = 5
• Is 5 in set {6, 2}? No
• Move pre forward

dummy -> 1 -> 3 -> 4 -> 5 -> 6
                        ↑
                       pre

Iteration 7:

• Check pre.next.val = 6
• Is 6 in set {6, 2}? Yes
• Skip node 6: pre.next = pre.next.next (which is None)

dummy -> 1 -> 3 -> 4 -> 5 -> None
                        ↑
                       pre

Step 4: Return Result

• pre.next is None, so the loop ends
• Return dummy.next, which points to node 1
• Final linked list: 1 -> 3 -> 4 -> 5

The algorithm successfully removed all nodes with values 2 and 6 from the original list.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm consists of two main operations:

1. Converting the array nums to a set, which takes O(n) time where n is the length of the array nums
2. Traversing the linked list once using a while loop that visits each node exactly once, which takes O(m) time where m is the length of the linked list head
3. For each node visited, checking membership in the set s is O(1) on average

Therefore, the total time complexity is O(n) + O(m) = O(n + m).

Space Complexity: O(n)

The algorithm uses additional space for:

1. The set s which stores all unique values from nums, requiring O(n) space where n is the length of the array nums
2. A few constant extra variables (pre, dummy) which take O(1) space

Therefore, the total space complexity is O(n) + O(1) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Advancing the Pointer After Removal

The Problem: A common mistake is to always advance the pointer after processing a node, like this:

while current.next:
    if current.next.val in values_to_remove:
        current.next = current.next.next
    current = current.next  # WRONG: Always advancing

This causes a bug because after removing a node, current.next already points to a new unchecked node. Moving current forward would skip checking this new node entirely.

Example of the Bug: Given list: 1 -> 2 -> 3 -> 4 and nums = [2, 3]

• Start: current points to dummy (before 1)
• Check node 1: not in set, move to node 1
• Check node 2: in set, remove it (now: 1 -> 3 -> 4)
• If we advance current here, we'd skip checking node 3!
• Result: 1 -> 3 -> 4 (incorrect, node 3 should be removed)

The Solution: Only advance the pointer when no removal occurs:

while current.next:
    if current.next.val in values_to_remove:
        current.next = current.next.next
        # Don't advance current here!
    else:
        current = current.next  # Only advance when keeping the node

Pitfall 2: Not Using a Dummy Node

The Problem: Trying to handle head removal without a dummy node leads to complex edge case handling:

# Without dummy node - complicated and error-prone
if head and head.val in values_to_remove:
    head = head.next
  
current = head
while current and current.next:
    if current.next.val in values_to_remove:
        current.next = current.next.next
    else:
        current = current.next
      
return head

This approach requires special handling for:

• Empty list
• Single node that needs removal
• Multiple consecutive removals at the start

The Solution: Always use a dummy node to simplify the logic:

dummy_node = ListNode(next=head)
current = dummy_node
# ... rest of the logic
return dummy_node.next

The dummy node ensures uniform handling of all nodes, including the head, without special cases.