Delete Nodes From Linked List Present in Array solution and explanation
Google
9 more videos on this problem
Delete Nodes From Linked List Present in Array | Simple | Dry Run | Leetcode 3217 | codestorywithMIKcodestorywithMIK · 15:19 · 10K views
Delete Nodes From Linked List Present in Array - Leetcode 3217 - PythonNeetCodeIO · 6:46 · 6K views
Delete Nodes From Linked List Present in Array - Leetcode 3217 - PythonNeetCodeIO · 6:47 · 4K views
3217. Delete Nodes From Linked List Present in Array (Leetcode Medium)Programming Live with Larry · 4:32 · 409 views
Daily Leetcode #2041: Nov 01, 2025 - 3217. Delete Nodes From Linked List Present in ArrayProgramming Live with Larry · 3:36 · 356 views
LeetCode Daily 3217 | Delete Nodes From Linked List Present in Array | Medium | Solution WalkthroughDaily Dose Of LeetCode · 15:30 · 172 views
3217. Delete Nodes From Linked List Present in Array | Leetcode Daily - PythonLeetcode Daily · 8:11 · 171 views
Delete Nodes From Linked List Present in Array - Leetcode 3217 - JavaCode With K5KC · 6:35 · 134 views
Leetcode | 3217 Delete Nodes From Linked List Present in Array | Java | LinkedList | HashsetCakot Coding · 12:43 · 96 views
Leetcode 3217 | Delete Nodes From Linked List Present in Array | Optimized Solution + CodeAlgo Optimizers · 7:32 · 60 views
The problem
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 <= 1051 <= nums[i] <= 105- All elements in
numsare 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.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def deleteNodes(head, nums):
lookup = set(nums)
dummy = ListNode(0)
dummy.next = head
prev, current = dummy, head
while current:
if current.val in lookup:
prev.next = current.next
else:
prev = current
current = current.next
return dummy.nextimport java.util.HashSet;
import java.util.Set;
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode deleteNodes(ListNode head, int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy, current = head;
while (current != null) {
if (set.contains(current.val)) {
prev.next = current.next;
} else {
prev = current;
}
current = current.next;
}
return dummy.next;
}
}#include <unordered_set>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* deleteNodes(ListNode* head, vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
ListNode* current = head;
while (current) {
if (s.count(current->val)) {
prev->next = current->next;
} else {
prev = current;
}
current = current->next;
}
return dummy->next;
}function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function deleteNodes(head, nums) {
const lookup = new Set(nums);
let dummy = new ListNode(0);
dummy.next = head;
let prev = dummy, current = head;
while (current) {
if (lookup.has(current.val)) {
prev.next = current.next;
} else {
prev = current;
}
current = current.next;
}
return dummy.next;
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* deleteNodes(struct ListNode* head, int* nums, int numsSize) {
bool lookup[100001] = { false };
for (int i = 0; i < numsSize; ++i) {
lookup[nums[i]] = true;
}
struct ListNode *dummy = malloc(sizeof(struct ListNode));
dummy->next = head;
struct ListNode *prev = dummy;
struct ListNode *current = head;
while (current != NULL) {
if (lookup[current->val]) {
prev->next = current->next;
} else {
prev = current;
}
current = current->next;
}
struct ListNode *newHead = dummy->next;
free(dummy);
return newHead;
}using System;
using System.Collections.Generic;
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode DeleteNodes(ListNode head, int[] nums) {
HashSet<int> set = new HashSet<int>(nums);
ListNode dummy = new ListNode(0) { next = head };
ListNode prev = dummy, curr = head;
while (curr != null) {
if (set.Contains(curr.val)) {
prev.next = curr.next;
} else {
prev = curr;
}
curr = curr.next;
}
return dummy.next;
}
}A set in Python is used for fast lookup of nodes to be removed. By using a dummy node, the algorithm handles node removal through pointer adjustments effectively.
Time Complexity: O(N + M), where N is the number of nodes and M is the size of nums.
Space Complexity: O(M).
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.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def deleteNodes(head, nums):
def is_in_array(val, nums):
return val in nums
dummy = ListNode(0)
dummy.next = head
prev, current = dummy, head
while current:
if is_in_array(current.val, nums):
prev.next = current.next
else:
prev = current
current = current.next
return dummy.nextclass ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public class Solution {
public ListNode deleteNodes(ListNode head, int[] nums) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy, current = head;
while (current != null) {
if (isInArray(current.val, nums)) {
prev.next = current.next;
} else {
prev = current;
}
current = current.next;
}
return dummy.next;
}
private boolean isInArray(int val, int[] nums) {
for (int n : nums) {
if (n == val) return true;
}
return false;
}
}#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
bool isInArray(int val, vector<int>& nums) {
for (int num : nums) {
if (num == val) return true;
}
return false;
}
ListNode* deleteNodes(ListNode* head, vector<int>& nums) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
ListNode* current = head;
while (current) {
if (isInArray(current->val, nums)) {
prev->next = current->next;
} else {
prev = current;
}
current = current->next;
}
return dummy->next;
}function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
function deleteNodes(head, nums) {
function isInArray(val, nums) {
return nums.includes(val);
}
let dummy = new ListNode(0);
dummy.next = head;
let prev = dummy, current = head;
while (current) {
if (isInArray(current.val, nums)) {
prev.next = current.next;
} else {
prev = current;
}
current = current.next;
}
return dummy.next;
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct ListNode {
int val;
struct ListNode *next;
};
bool isInArray(int val, int* nums, int numsSize) {
for (int i = 0; i < numsSize; ++i) {
if (nums[i] == val) return true;
}
return false;
}
struct ListNode* deleteNodes(struct ListNode* head, int* nums, int numsSize) {
struct ListNode* dummy = malloc(sizeof(struct ListNode));
dummy->next = head;
struct ListNode* prev = dummy;
struct ListNode* current = head;
while (current != NULL) {
if (isInArray(current->val, nums, numsSize)) {
prev->next = current->next;
} else {
prev = current;
}
current = current->next;
}
struct ListNode* newHead = dummy->next;
free(dummy);
return newHead;
}public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode DeleteNodes(ListNode head, int[] nums) {
ListNode dummy = new ListNode(0) { next = head };
ListNode prev = dummy, curr = head;
while (curr != null) {
if (IsInArray(curr.val, nums)) {
prev.next = curr.next;
} else {
prev = curr;
}
curr = curr.next;
}
return dummy.next;
}
private bool IsInArray(int val, int[] nums) {
foreach (int n in nums) {
if (n == val) return true;
}
return false;
}
}The Python code utilizes list membership checking instead of a hash structure, achieving in-place node management without additional memory allocations for lookup.
Time Complexity: O(N * M), where N is the linked list length and M is nums size.
Space Complexity: O(1) extra space for operations, without using additional collections.
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.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function modifiedList(nums: number[], head: ListNode | null): ListNode | null {
const s: Set<number> = new Set(nums);
const dummy = new ListNode(0, head);
for (let pre = dummy; pre.next; ) {
if (s.has(pre.next.val)) {
pre.next = pre.next.next;
} else {
pre = pre.next;
}
}
return dummy.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func modifiedList(nums []int, head *ListNode) *ListNode {
s := map[int]bool{}
for _, x := range nums {
s[x] = true
}
dummy := &ListNode{Next: head}
for pre := dummy; pre.Next != nil; {
if s[pre.Next.Val] {
pre.Next = pre.Next.Next
} else {
pre = pre.Next
}
}
return dummy.Next
}// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
// pub val: i32,
// pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
// #[inline]
// fn new(val: i32) -> Self {
// ListNode {
// next: None,
// val
// }
// }
// }
use std::collections::HashSet;
impl Solution {
pub fn modified_list(nums: Vec<i32>, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let s: HashSet<i32> = nums.into_iter().collect();
let mut dummy = Box::new(ListNode { val: 0, next: head });
let mut pre = &mut dummy;
while let Some(ref mut node) = pre.next {
if s.contains(&node.val) {
pre.next = node.next.take();
} else {
pre = pre.next.as_mut().unwrap();
}
}
dummy.next
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Set-Based Filtering of Linked List | Time Complexity: O(N + M), where N is the number of nodes and M is the size of nums. |
| Two-Pointer Technique Without Extra Space | Time Complexity: O(N * M), where N is the linked list length and M is nums size. |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Set-Based Filtering of Linked List | O(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 Space | O(n * m) | O(1) | Useful when memory usage must stay minimal or when the array size is very small. |
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.