We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delete Nodes From Linked List Present in Array

Number: 3501

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Google

Problem Description

Given an unsorted linked list and an array of unique integers (nums), remove all nodes from the linked list whose values appear in nums and return the modified linked list.

Key Insights

  • Convert the array nums into a set to allow constant time lookups.
  • Use a dummy node to handle edge cases where the head might be removed.
  • Traverse the linked list and remove any node whose value is present in the set.
  • Maintain a pointer to the previous node to adjust pointers when skipping nodes.

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of nodes in the linked list and m is the length of nums.
Space Complexity: O(m) due to the additional set storing the nums.

Solution

We first convert the nums array into a set for efficient membership checking. A dummy node is created to link before the head of the list, making it easier to handle deletions at the front of the list. We then traverse the list with two pointers: one (prev) that trails behind the current pointer. If the current node's value is present in the set, we adjust prev.next to skip the current node; otherwise, we move the prev pointer forward. Finally, the modified list starting from dummy.next is returned.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteNodes(nums, head):
    # Create a set from nums for O(1) membership checking
    nums_set = set(nums)
    
    # Create dummy node pointing to head to simplify deletion logic
    dummy = ListNode(0)
    dummy.next = head
    
    # Initialize pointers: prev starts at dummy, current starts at head
    prev, current = dummy, head
    
    while current:
        if current.val in nums_set:
            # Skip the current node by linking prev.next to current.next
            prev.next = current.next
        else:
            # Move prev pointer forward when current node is not to be deleted
            prev = current
        # Advance current pointer to the next node
        current = current.next
        
    return dummy.next
← Back to All Questions