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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Delete Nodes From Linked List Present in Array

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires filtering a linked list based on values present in an array.
  • A hash set can be utilized to store the values from the array for O(1) lookups.
  • We need to handle cases where nodes to be deleted are at the beginning, middle, or end of the linked list.

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of nodes in the linked list and m is the size of the nums array.
Space Complexity: O(m) for storing the values in the hash set.

Solution

To solve this problem, we can use the following approach:

  1. Create a hash set from the nums array to allow for quick lookups.
  2. Initialize a dummy node to handle edge cases easily (like removing the head node).
  3. Traverse the linked list and check if each node's value is in the hash set.
  4. If a node's value is found in the hash set, skip it by adjusting the pointers.
  5. If a node's value is not in the hash set, maintain it in the resulting linked list.
  6. Finally, return the next node from the dummy node, which represents the new head of the modified linked list.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteNodes(nums, head):
    nums_set = set(nums)  # Create a set for O(1) lookups
    dummy = ListNode(0)   # Dummy node to simplify operations
    current = dummy        # Pointer to build the new list

    while head:            # Traverse the linked list
        if head.val not in nums_set:  # If value not in nums
            current.next = head  # Link the current node
            current = current.next  # Move current pointer
        head = head.next  # Move to the next node

    current.next = None  # Terminate the new list
    return dummy.next    # Return the new head
← Back to All Questions