Delete Nodes From Linked List Present in Array

main.md

Question

Approach

I first convert nums into a set for O(1) lookups. Then, I use a dummy node to simplify edge cases like when the head itself needs to be removed. I traverse the linked list with a pointer. If the current node’s value is in the set, I skip it by linking to curr.next; otherwise, I move forward. Finally, I return dummy.next as the new head of the modified list.

Implementation

class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        remove = set(nums)
        dummy = ListNode(0)
        dummy.next = head
        curr = dummy
        
        while curr.next:
            if curr.next.val in remove:
                curr.next = curr.next.next
            else:
                curr = curr.next
                
        return dummy.next

Complexities

• Time: O(n + m), where n is the number of nodes and m is the size of nums
• Space: O(m)