Problem of The Day: Delete Nodes From Linked List Present in Array

Problem Statement

Intuition

The goal is to modify the linked list by removing nodes whose values are present in the given list nums. My first thought is to use a set for quick lookup of values from nums, and then traverse the linked list while skipping nodes that match the values in the set.

Approach

1. Convert the list nums into a set for faster lookups.
2. Use a sentinel node to handle edge cases (e.g., when the head node itself needs to be removed).
3. Traverse the linked list, and for each node:
   • If the node’s value is in the set, skip it.
   • Otherwise, link it to the previous node.
4. Return the modified list starting from the node next to the sentinel.

Complexity

• Time complexity: The time complexity is \(O(n + m)\) where n is the number of nodes in the linked list and m is the number of elements in the nums list. This is because we convert nums to a set in \(O(m)\) and then traverse the linked list in \(O(n)\).

• Space complexity: The space complexity is \(O(m)\) because we store nums in a set.

Code

# 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]:
        nums_set = set(nums)
        curr = head
        sentinel = ListNode(-1, head)
        prev = sentinel
        while curr:
            if curr.val in nums_set:
                curr = curr.next
            else:
                prev.next = curr
                prev = curr
                curr = curr.next
        prev.next = curr
        return sentinel.next

Editorial

Approach: Hash Set

class Solution:
    def modifiedList(
        self, nums: List[int], head: Optional[ListNode]
    ) -> Optional[ListNode]:
        # Create a set for efficient lookup of values in nums
        values_to_remove = set(nums)

        # Handle the case where the head node needs to be removed
        while head and head.val in values_to_remove:
            head = head.next

        # If the list is empty after removing head nodes, return None
        if not head:
            return None

        # Iterate through the list, removing nodes with values in the set
        current = head
        while current.next:
            if current.next.val in values_to_remove:
                # Skip the next node by updating the pointer
                current.next = current.next.next
            else:
                # Move to the next node
                current = current.next

        return head