# Delete Nodes From Linked List Present in Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/delete-nodes-from-linked-list-present-in-array)
Canonical: https://scaleengineer.com/dsa/problems/delete-nodes-from-linked-list-present-in-array
**Data structures:** Array, Hash Table, Linked List
---
## 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:**

**![](https://assets.glich.co/dsa/delete-nodes-from-linked-list-present-in-array/image0.png)**

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:**

![](https://assets.glich.co/dsa/delete-nodes-from-linked-list-present-in-array/image1.png)

Remove the nodes with value 1.

**Example 3:**

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

**Output:** \[1,2,3,4\]

**Explanation:**

**![](https://assets.glich.co/dsa/delete-nodes-from-linked-list-present-in-array/image2.png)**

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`.

# Approaches
## Brute Force with Nested Loops
This approach involves iterating through each node of the linked list and, for each node, scanning the entire `nums` array to check if the node's value should be deleted. It is the most straightforward but least efficient method.
**Time:** O(N * M), where N is the number of nodes in the linked list and M is the number of elements in the `nums` array. For each of the N nodes, we perform a linear scan of the M elements in `nums`. · **Space:** O(1). We only use a few extra pointers (`dummy`, `prev`, `current`) regardless of the input size.
**Pros:** Simple to understand and implement.; Constant space complexity, as it doesn't use any auxiliary data structures that scale with input size.
**Cons:** Highly inefficient with a time complexity of O(N * M), where N is the number of nodes and M is the length of the `nums` array.; Will likely result in a 'Time Limit Exceeded' (TLE) error on platforms with large test cases.
### Explanation
The brute-force method directly translates the problem statement into code. We traverse the linked list from head to tail. For each node we encounter, we perform a second traversal, this time through the `nums` array, to check if the node's value exists in the array.

To facilitate the deletion of nodes, including the head node, we use a `dummy` node. The `dummy` node's `next` pointer is set to the original `head`. We then use two pointers, `prev` and `current`, to iterate through the list. `prev` always points to the last node that was kept, and `current` points to the node being inspected.

If `current.val` is found in `nums`, we remove the `current` node by linking `prev` to `current.next`. If `current.val` is not in `nums`, we keep the node by advancing `prev` to `current`. The `current` pointer is always advanced to the next node in the list in each step.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode modifiedList(int[] nums, ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode prev = dummy;
        ListNode current = head;
        
        while (current != null) {
            boolean toDelete = false;
            for (int num : nums) {
                if (current.val == num) {
                    toDelete = true;
                    break;
                }
            }
            
            if (toDelete) {
                // Delete current node by skipping it
                prev.next = current.next;
            } else {
                // Keep current node, so move prev forward
                prev = current;
            }
            // Move to the next node for the next iteration
            current = current.next;
        }
        
        return dummy.next;
    }
}
```
### Algorithm
- Create a dummy node and point its `next` to the `head` of the list. This simplifies handling cases where the head node itself needs to be deleted. 
- Initialize two pointers, `prev = dummy` and `current = head`.
- Traverse the list using the `current` pointer until it becomes `null`.
- For each `current` node, iterate through the entire `nums` array.
- If `current.val` is found in `nums`, set a flag `toDelete = true` and break the inner loop.
- After the inner loop, if `toDelete` is true, bypass the `current` node by setting `prev.next = current.next`. The `prev` pointer does not move.
- If `toDelete` is false, it means the node should be kept. Advance the `prev` pointer: `prev = current`.
- In every iteration of the outer loop, advance the `current` pointer to the next node: `current = current.next`.
- After the loop finishes, return `dummy.next`, which points to the head of the modified list.

## Optimized Approach using a HashSet
This approach significantly improves performance by first storing all values from the `nums` array into a HashSet. This allows for checking if a node's value needs to be deleted in constant average time, reducing the overall time complexity from quadratic to linear.
**Time:** O(N + M), where N is the number of nodes and M is the length of `nums`. It takes O(M) to build the HashSet and O(N) to traverse the linked list, with each node check being O(1) on average. · **Space:** O(M). The space is dominated by the HashSet used to store the M elements from the `nums` array.
**Pros:** Highly efficient with a linear time complexity of O(N + M).; This is the optimal approach for the given constraints and passes all test cases efficiently.
**Cons:** Requires extra space of O(M) to store the elements of `nums` in a HashSet.
### Explanation
To optimize the process, we can eliminate the costly repeated searches in the `nums` array. The key idea is to use a data structure that provides near-constant time lookups. A `HashSet` is a perfect choice for this.

First, we iterate through the `nums` array and store all its elements in a `HashSet`. This pre-processing step allows us to later check for the existence of a value in O(1) average time.

After building the set, we traverse the linked list using the same `dummy` node and `prev`/`current` pointer technique as in the brute-force approach. However, for each `current` node, instead of looping through `nums`, we simply perform a `set.contains(current.val)` check.

If the value is in the set, we delete the node (`prev.next = current.next`). Otherwise, we keep it and advance `prev` (`prev = current`). This reduces the time complexity from quadratic to linear, making it an efficient solution.

```java
import java.util.HashSet;
import java.util.Set;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode modifiedList(int[] nums, ListNode head) {
        // Step 1: Create a HashSet for O(1) average time lookups.
        Set<Integer> numsSet = new HashSet<>();
        for (int num : nums) {
            numsSet.add(num);
        }
        
        // Step 2: Use a dummy node to simplify head deletion.
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode prev = dummy;
        ListNode current = head;
        
        // Step 3: Traverse the linked list.
        while (current != null) {
            // Step 4: Check if the current node's value is in the set.
            if (numsSet.contains(current.val)) {
                // If yes, bypass the current node.
                prev.next = current.next;
            } else {
                // If no, this node is kept. Move prev to current.
                prev = current;
            }
            // Move to the next node in the original list.
            current = current.next;
        }
        
        // The modified list starts at dummy.next.
        return dummy.next;
    }
}
```
### Algorithm
- Create a `HashSet` of integers.
- Iterate through the `nums` array and add each element to the `HashSet`. This takes O(M) time.
- Create a dummy node and point its `next` to the `head` of the list.
- Initialize two pointers, `prev = dummy` and `current = head`.
- Traverse the list using the `current` pointer until it becomes `null`.
- For each `current` node, check if its value is present in the `HashSet` using `set.contains(current.val)`. This is an O(1) average time operation.
- If the value is in the set, bypass the `current` node by setting `prev.next = current.next`.
- Otherwise, the node is kept, so we advance the `prev` pointer: `prev = current`.
- In every iteration, advance the `current` pointer: `current = current.next`.
- Return `dummy.next`.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode modifiedList ( int [] nums , ListNode head ) { Set < Integer > s = new HashSet <>(); for ( int x : nums ) { s . add ( x ); } ListNode dummy = new ListNode ( 0 , head ); for ( ListNode pre = dummy ; pre . next != null ;) { if ( s . contains ( pre . next . val )) { pre . next = pre . next . next ; } else { pre = pre . next ; } } return dummy . next ; } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * modifiedList ( vector < int >& nums , ListNode * head ) { unordered_set < int > s ( nums . begin (), nums . end ()); ListNode * dummy = new ListNode ( 0 , head ); for ( ListNode * pre = dummy ; pre -> next ;) { if ( s . count ( pre -> next -> val )) { pre -> next = pre -> next -> next ; } else { pre = pre -> next ; } } return dummy -> next ; } };
```

### Python

```python
# 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
```