#3217

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Delete Nodes From Linked List Present in Array

Remove nodes from a linked list if their values exist in a given array.

Problem Statement

Given an array of integers nums and the head of a linked list, you are tasked with removing all nodes from the linked list that have a value that exists in the array nums.

For example, if nums = [1,2,3] and the linked list is head = [1,2,3,4,5], the resulting list after removing nodes with values from nums would be head = [4,5]. The input guarantees that at least one node in the list does not have a value present in nums.

Examples

Example 1

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

Output: [4,5]

Remove the nodes with values 1, 2, and 3.

Example 2

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

Output: [2,2,2]

Remove the nodes with value 1.

Example 3

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

Output: [1,2,3,4]

No node has value 5.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 105
All elements in nums are unique.
The number of nodes in the given list is in the range [1, 105].
1 <= Node.val <= 105
The input is generated such that there is at least one node in the linked list that has a value not present in nums.

Solution Approach

Use a HashSet for Efficient Lookups

First, convert the nums array into a HashSet to allow O(1) average time complexity for checking if a value should be removed from the linked list.

Traverse and Modify the Linked List

Iterate through the linked list. For each node, check if its value is in the HashSet. If it is, skip the node by adjusting the pointers. If it isn’t, retain the node in the list.

Edge Case Handling

Ensure that edge cases like an empty list or when no nodes need to be deleted are handled properly. For an empty list, simply return null. For lists where no deletions are needed, return the original list unchanged.

Complexity Analysis

Metric	Value
Time	O(m + n)
Space	O(m)

The time complexity is O(m + n), where m is the number of nodes in the linked list, and n is the size of the nums array. The space complexity is O(n), as we store the elements of nums in a HashSet.

What Interviewers Usually Probe

The candidate effectively uses a HashSet for O(1) lookups, indicating a solid understanding of hashing and time complexity trade-offs.
The solution demonstrates proficiency in traversing and modifying linked lists in-place, which is a common interview pattern.
The candidate handles edge cases well, ensuring the solution works for both empty lists and lists that require no deletions.

Common Pitfalls or Variants

Common pitfalls

Not using a HashSet for quick lookups, which could lead to an inefficient solution with O(n) lookups for each node.
Incorrect pointer manipulation while skipping nodes, which can break the linked list structure and lead to memory leaks or infinite loops.
Failing to account for cases where no deletions are needed or when the list is empty.

Follow-up variants

The problem can be extended to delete nodes based on multiple arrays rather than a single one.
Instead of removing nodes in-place, the candidate could return a new linked list with the nodes that remain.
Another variant could involve sorting the linked list before deleting nodes, which may have additional time complexity considerations.

FAQ

What is the best way to handle the deletion of nodes in a linked list?

The best approach is to use a HashSet to store the values from the array, and then iterate through the linked list to remove the nodes by adjusting pointers based on the HashSet lookups.

How does the time complexity of this solution compare to others?

The time complexity of this solution is O(m + n), where m is the number of nodes and n is the number of elements in the array, which is optimal for this type of problem.

What happens if no nodes need to be deleted from the linked list?

If no nodes need to be deleted, the original linked list is returned unchanged. The solution should handle this case by simply returning the original list if no deletions are made.

Can this problem be solved with a brute force approach?

Yes, a brute force approach would involve checking each node’s value against the entire array for every node, leading to an O(m * n) time complexity, which is inefficient compared to the optimal solution using a HashSet.

Is it possible to optimize this problem further?

The current solution is optimal in terms of time complexity, but if space is a concern, alternative methods like using two pointers may be explored, although they typically introduce more complexity.

terminal

Solution

Solution 1: Hash Table

We can use a hash table $\textit{s}$ to store all the elements in the array $\textit{nums}$. Then, we define a dummy node $\textit{dummy}$ and point it to the head node of the list $\textit{head}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def modifiedList(
        self, nums: List[int], head: Optional[ListNode]
    ) -> Optional[ListNode]:
        s = set(nums)
        pre = dummy = ListNode(next=head)
        while pre.next:
            if pre.next.val in s:
                pre.next = pre.next.next
            else:
                pre = pre.next
        return dummy.next

Continue Practicing

#3507 minimum pair removal to sort array i #3510 minimum pair removal to sort array ii #3224 minimum array changes to make differences equal