LeetCode 3217 - Delete Nodes From Linked List Present in Array

LeetCode Problem 3217

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Linked List

Solution

Problem Understanding

This problem asks us to modify a singly linked list by removing all nodes whose values appear in a given array nums. The input consists of two elements: an array of integers nums and the head of a linked list. Each node in the linked list contains an integer value and a pointer to the next node. The output is the head of the linked list after all nodes with values in nums have been deleted.

The constraints indicate that the array nums can be large, up to 100,000 elements, and the linked list can also have up to 100,000 nodes. Values in nums are unique and all node values in the list are positive integers within the same range. Importantly, the input guarantees that there is at least one node in the linked list that is not present in nums, ensuring the result is never empty.

Key edge cases include situations where nodes to remove are at the head of the list, consecutive nodes, or none of the nodes match nums. Naive solutions that scan the list for each element in nums could become very slow due to these constraints.

Approaches

The brute-force approach would be to iterate over each element in nums and, for each value, traverse the entire linked list to remove matching nodes. This approach works correctly because it explicitly deletes each node with a value in nums, but it is inefficient. If the list has n nodes and nums has m elements, the time complexity would be O(m * n), which is impractical for large inputs.

The optimal approach leverages a hash set to store all values from nums. This allows O(1) average-time checks to see if a node needs to be removed. We then traverse the linked list once, removing nodes in-place when their values exist in the hash set. This reduces the time complexity to O(n + m), which is efficient even for the maximum constraints. We use a dummy node to simplify handling deletions at the head.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m * n)	O(1)	Iterate through the list for every element in nums
Optimal	O(n + m)	O(m)	Use a hash set for O(1) lookup, single pass through the linked list

Algorithm Walkthrough

1. Create a hash set from nums: This allows O(1) average lookup to check whether a node should be removed.
2. Initialize a dummy node: The dummy node points to the head of the list. This simplifies handling edge cases where the head itself must be removed.
3. Set a pointer current to the dummy node: We will traverse the linked list using current.next so we can easily remove nodes by updating current.next.
4. Traverse the list: While current.next is not null, check if current.next.val is in the hash set. If it is, skip the node by setting current.next = current.next.next. If it is not, move current forward to current.next.
5. Return dummy.next: This is the new head of the modified list, which may have changed if the original head was removed.

Why it works: The algorithm maintains the invariant that current always points to the last node that is guaranteed to remain in the list. Any node after current is either skipped if it should be removed or retained. Using a dummy node ensures that removal at the head is handled seamlessly.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import List, Optional

class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        remove_set = set(nums)
        dummy = ListNode(-1)
        dummy.next = head
        current = dummy
        
        while current.next:
            if current.next.val in remove_set:
                current.next = current.next.next
            else:
                current = current.next
        
        return dummy.next

The Python solution first converts nums into a set for fast lookup. A dummy node simplifies deletion at the head. The while loop iterates through each node exactly once, removing nodes whose values are in the set and preserving all others. Returning dummy.next ensures the correct new head.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func modifiedList(nums []int, head *ListNode) *ListNode {
    removeSet := make(map[int]struct{})
    for _, num := range nums {
        removeSet[num] = struct{}{}
    }
    
    dummy := &ListNode{Val: -1, Next: head}
    current := dummy
    
    for current.Next != nil {
        if _, exists := removeSet[current.Next.Val]; exists {
            current.Next = current.Next.Next
        } else {
            current = current.Next
        }
    }
    
    return dummy.Next
}

In Go, the main difference is that we use a map with empty struct values to represent a set. The dummy node is allocated as a pointer, and node traversal and deletion are handled in the same way as in Python. Nil checks are implicit in the for current.Next != nil condition.

Worked Examples

Example 1: nums = [1,2,3], head = [1,2,3,4,5]

Step	current.val	current.next.val	Action	Resulting List
0	-1	1	Remove 1	-1->2->3->4->5
1	-1	2	Remove 2	-1->3->4->5
2	-1	3	Remove 3	-1->4->5
3	-1	4	Keep 4	-1->4->5
4	4	5	Keep 5	-1->4->5
End	5	nil	Done	4->5

Example 2: nums = [1], head = [1,2,1,2,1,2]

The algorithm removes all nodes with value 1, retaining all nodes with value 2. The resulting list is 2->2->2.

Example 3: nums = [5], head = [1,2,3,4]

No nodes match nums, so the list remains unchanged.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Building the set takes O(m), traversing the linked list takes O(n)
Space	O(m)	The set stores all elements from nums

The algorithm is efficient for large inputs because it avoids nested iterations. Using a hash set ensures each node is checked in O(1) average time.

Test Cases

# test cases
# Example 1
assert str(Solution().modifiedList([1,2,3], ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))))) == "4->5"  # removes 1,2,3

# Example 2
assert str(Solution().modifiedList([1], ListNode(1, ListNode(2, ListNode(1, ListNode(2, ListNode(1, ListNode(2)))))))) == "2->2->2"  # removes 1

# Example 3
assert str(Solution().modifiedList([5], ListNode(1, ListNode(2, ListNode(3, ListNode(4)))))) == "1->2->3->4"  # nothing removed

# Edge case: head node removed
assert str(Solution().modifiedList([1], ListNode(1, ListNode(2)))) == "2"  # head removed

# Edge case: consecutive nodes removed
assert str(Solution().modifiedList([2], ListNode(1, ListNode(2, ListNode(2, ListNode(3)))))) == "1->3"  # consecutive removed

# Edge case: all nodes removed except one
assert str(Solution().modifiedList([1,2,3,4], ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))))) == "5"  # only last remains

Test	Why
Remove multiple nodes	Validates removal of several nodes from head and middle
Remove alternating nodes	Ensures non-consecutive removals work
No nodes removed	Validates that list remains unchanged
Head node removed	Tests removal at head edge case
Consecutive nodes removed	Ensures links are correctly updated
Only one node remains	Checks handling when almost all nodes are removed

Edge Cases

First, consider when the head node itself needs removal. Without a dummy node, removing the head would require special handling, but using a dummy node allows uniform deletion logic. Second,