Skip to main content
Talentd

Delete Nodes From Linked List Present in Array - Solution & Explanation

MediumArrayHash TableLinked List18 min readAsked at: Amazon, Microsoft, Meta +2
Practice this problem

Problem Statement

You are given an array of integers nums and the head of a linked list. Return the head of the modified linked list after removing all nodes from the linked list that have a value that exists in nums.

 

Example 1:

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

Output: [4,5]

Explanation:

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]

Explanation:

Remove the nodes with value 1.

Example 3:

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

Output: [1,2,3,4]

Explanation:

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.

Approach Overview

Problem Overview: You receive an integer array and the head of a linked list. Any node whose value exists in the array must be removed from the list. The result should be the filtered linked list that keeps only values not present in the array.

Approach 1: Set-Based Filtering of Linked List (Time: O(n + m), Space: O(m))

The most practical solution converts the array into a hash set for constant-time membership checks. Insert every value from the array into the set, then iterate through the linked list. For each node, check whether node.val exists in the set. If it does, bypass the node by updating the previous node's next pointer. If not, keep the node and continue traversing.

This approach works well because hash table lookups run in average O(1) time. Building the set takes O(m) where m is the array size, and scanning the linked list takes O(n). The total time complexity becomes O(n + m) with O(m) extra space. This is the cleanest and most scalable solution when the array can be large.

Approach 2: Two-Pointer Technique Without Extra Space (Time: O(n * m), Space: O(1))

If extra memory is restricted, you can avoid a hash set and instead check each node directly against the array. Traverse the linked list with two pointers: prev and curr. For every node, scan the entire array to determine whether the value should be removed. If the value appears in the array, update prev.next to skip the current node. Otherwise, move both pointers forward.

This technique uses constant auxiliary space since no additional data structures are created. The downside is performance. Each linked list node may require scanning the entire array, resulting in O(n * m) time. It works only when the array is small or memory constraints are strict.

Recommended for interviews: The hash set filtering approach is what most interviewers expect. It demonstrates that you recognize when to trade a small amount of memory for a large performance gain. The two-pointer approach without extra space is still useful to discuss because it shows awareness of memory constraints and algorithmic trade-offs.

Approach 1: Set-Based Filtering of Linked List

This approach uses a set for fast lookup of values that need to be removed from the linked list. By iterating through the linked list and checking if each node's value is in the set, we can efficiently determine which nodes to skip and which to keep.

The solution initializes a boolean array lookup to quickly check if a node value should be removed. As we traverse the list, we either skip or keep nodes based on the contents of lookup. A dummy node simplifies edge cases, like removing the list's head.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N + M), where N is the length of the linked list and M is the size of nums.
Space Complexity: O(M), where M is the size of nums.

Try this approach in the editor →

Approach 2: Two-Pointer Technique Without Extra Space

This approach leverages a two-pointer technique where the result is constructed in-place. Although it doesn't require extra storage for the set, it does involve modifications that make subsequent operations more complex in favor of reducing space usage.

The C solution avoids extra space by implementing a linear search function isInArray that checks for value presence within the nums array, although less efficient than using a set for larger inputs.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N * M), where N is the length of the linked list and M is the size of nums.
Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Hash Table

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

Next, we traverse the list starting from the dummy node dummy. If the value of the next node of the current node is in the hash table s, we make the current node point to the next next node; otherwise, we move the current node pointer to the next node.

Finally, we return the next node of the dummy node dummy.

The time complexity is O(n + m), and the space complexity is O(n). Here, n is the length of the array nums, and m is the length of the list head.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Set-Based Filtering of Linked List

Time Complexity: O(N + M), where N is the length of the linked list and M is the size of nums.
Space Complexity: O(M), where M is the size of nums.

Two-Pointer Technique Without Extra Space

Time Complexity: O(N * M), where N is the length of the linked list and M is the size of nums.
Space Complexity: O(1).

Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Set-Based Filtering of Linked ListO(n + m)O(m)General case. Fast lookups using a hash set make it the optimal and most scalable approach.
Two-Pointer Technique Without Extra SpaceO(n * m)O(1)Useful when memory usage must stay minimal or when the array size is very small.

Video Solution

Delete Nodes From Linked List Present in Array | Simple | Dry Run | Leetcode 3217 | codestorywithMIK • codestorywithMIK • 10,041 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Delete Nodes From Linked List Present in Array easy or hard?
The problem is rated Medium because it combines two concepts: linked list manipulation and hash-based lookups. The logic is straightforward once you recognize that a set eliminates repeated array scans.
How to solve Delete Nodes From Linked List Present in Array in O(n)?
Achieve near-linear performance by storing array values in a hash set first. Traverse the linked list once and remove nodes whose values appear in the set. Each lookup is O(1), so the total runtime becomes O(n + m).
What is the best approach for Delete Nodes From Linked List Present in Array?
The best approach uses a hash set to store all values from the array, then scans the linked list once. Each node value is checked against the set in O(1) time. This results in O(n + m) time complexity and O(m) extra space, which is optimal for large inputs.
What data structure is used in Delete Nodes From Linked List Present in Array?
The optimal solution uses a hash set to store array values and a singly linked list traversal to remove matching nodes. The hash set enables constant-time membership checks while iterating through the list.
What is the time complexity of Delete Nodes From Linked List Present in Array?
Using a hash set, the total time complexity is O(n + m) where n is the number of linked list nodes and m is the array size. Building the set takes O(m) and traversing the linked list takes O(n). A no-extra-space approach increases complexity to O(n * m).
Delete Nodes From Linked List Present in Array Python or Java solution approach
Python and Java implementations typically build a HashSet from the array and iterate through the linked list with a previous pointer. If the current node value exists in the set, update prev.next to skip it. Otherwise move both pointers forward.
Is Delete Nodes From Linked List Present in Array asked at Google, Amazon, or Meta?
Linked list filtering and hash set lookup problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often test whether candidates recognize when to use a hash table to eliminate repeated searches.

Ready to solve this problem?

Practice Delete Nodes From Linked List Present in Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Delete Node in a Linked List

Next

Remove Linked List Elements