Delete Nodes From Linked List Present in Array

Delete Nodes From Linked List Present in Array

1. What is this problem about?

The Delete Nodes From Linked List Present in Array interview question involves filtering a linear data structure based on a set of prohibited values. You are given the head of a linked list and an array of integers. Your goal is to remove every node from the list whose value exists in the given array. This Delete Nodes From Linked List Present in Array coding problem is a fundamental test of combining multiple data structures for efficiency.

2. Why is this asked in interviews?

Companies like Microsoft and Amazon ask this to see if you can optimize a search operation. If you check the array for every node in the list using a linear search, the time complexity becomes $O(N imes M)$, where $N$ is the list length and $M$ is the array size. Interviewers want to see you use a Hash Table interview pattern to reduce this to $O(N + M)$.

3. Algorithmic pattern used

This problem uses a Hash Set for $O(1)$ lookups combined with a Linked List Traversal.

• First, convert the input array into a Hash Set.
• Use a "dummy head" node to handle cases where the original head needs to be deleted.
• Traverse the list, checking if the next node's value is in the set.
• If it is, skip the node by re-linking the pointers.

4. Example explanation

Suppose the list is 10 -> 20 -> 30 -> 40 and the array is [20, 40].

1. Put [20, 40] into a set.
2. Start at a dummy node pointing to 10.
3. Check 10: Not in set. Move to 10.
4. Check 20: IN SET! Change 10.next to point to 30.
5. Check 30: Not in set. Move to 30.
6. Check 40: IN SET! Change 30.next to null. Final List: 10 -> 30.

5. Common mistakes candidates make

• Inefficient Search: Searching the array directly ($O(M)$) for every node instead of using a set ($O(1)$).
• Missing the Head: Failing to handle the case where the first node (the head) itself needs to be deleted.
• Memory Leaks: In languages like C++, forgetting to free the memory of the deleted nodes.

6. Interview preparation tip

Always use a Dummy Node when you need to delete nodes from a linked list. It simplifies the logic significantly by ensuring the node you are deleting always has a "previous" node to link from, even if it's the very first element.