Delete Nodes From Linked List Present in Array

Delete Nodes From Linked List Present in Array - 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.

The linked list is represented as a sequence of nodes where each node contains an integer value and a pointer to the next node. After removal, the remaining nodes should maintain their original relative order.

Input & Output

Example 1 — Basic Deletion

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

› Output: [4,5]

💡 Note: Remove nodes with values 1, 2, 3 from the linked list. Only nodes with values 4 and 5 remain.

Example 2 — Partial Deletion

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

› Output: [2,2,2]

💡 Note: Remove all nodes with value 1. The three nodes with value 2 remain in their original order.

Example 3 — No Deletion

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

› Output: [1,2,3,4]

💡 Note: No nodes have value 5, so the entire linked list remains unchanged.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵
The number of nodes in the linked list is in the range [1, 10⁵]
1 ≤ Node.val ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums=[1,2,3] and linked list [1,2,3,4,5]

Filter

Remove nodes whose values exist in nums array

Output

Remaining linked list [4,5] maintains original order

Key Takeaway

🎯 Key Insight: Hash set enables O(1) lookups instead of O(m) array scans, transforming O(n×m) to O(n+m)

Asked in

A Amazon 15 M Microsoft 12 G Google 8

The key insight is to use a hash set for O(1) lookups instead of O(m) array searches. Best approach converts nums to hash set, then traverses the linked list once, removing nodes found in the set. Time: O(n+m), Space: O(m)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Array Search	O(n×m)	O(1)	For each node, search through the entire nums array to check if it should be deleted
Hash Set Optimization	O(n+m)	O(m)	Convert nums array to hash set for O(1) lookup, then traverse list once

Brute Force Array Search — Algorithm Steps

Create dummy head to handle edge cases
For each node, search entire nums array
If value found, skip node by adjusting pointers
Continue until end of list

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Node

For current node, search through all of nums array

Linear Search

Compare node value with each element in nums

Remove or Keep

If found in nums, skip node; otherwise keep it

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(int* nums, int numsSize, struct ListNode* head) {
    // Create dummy head to handle edge cases
    struct ListNode dummy = {0, head};
    struct ListNode* prev = &dummy;
    struct ListNode* current = head;
    
    while (current) {
        // Search for current value in nums array
        int shouldDelete = 0;
        for (int i = 0; i < numsSize; i++) {
            if (current->val == nums[i]) {
                shouldDelete = 1;
                break;
            }
        }
        
        if (shouldDelete) {
            // Skip this node
            prev->next = current->next;
        } else {
            // Keep this node
            prev = current;
        }
        
        current = current->next;
    }
    
    return dummy.next;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = malloc(sizeof(struct ListNode));
        current->next->val = arr[i];
        current->next->next = NULL;
        current = current->next;
    }
    return head;
}

void printList(struct ListNode* head) {
    printf("[");
    int first = 1;
    while (head) {
        if (!first) printf(",");
        printf("%d", head->val);
        first = 0;
        head = head->next;
    }
    printf("]\n");
}

int main() {
    char line[1000];
    
    // Read nums array
    fgets(line, sizeof(line), stdin);
    int nums[100];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Read head array
    fgets(line, sizeof(line), stdin);
    int headArr[100];
    int headSize = 0;
    token = strtok(line + 1, ",]");
    while (token) {
        headArr[headSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    struct ListNode* head = arrayToList(headArr, headSize);
    struct ListNode* result = solution(nums, numsSize, head);
    printList(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

For each of n nodes in list, search through m elements in nums array

✓ Linear Growth

Space Complexity

O(1)

Only using a few pointer variables, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Array Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler