Problem Statement in English

Given a linked list and an array of values, delete all nodes from the linked list that have values present in the array.

Return the new head of the modified linked list.

Approach

To solve this problem, we can use a set to store the values present in the array for O(1) lookup time.

We will then traverse the linked list, and for each node, we will check if its value is in the set. If it is not, we will link it to the previous node; otherwise, we will skip it.

Just to help with implementation, we can use a dummy head node that points to the original head of the linked list. This way, we can easily handle cases where the head itself needs to be deleted.

Solution in Python


class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        blocked = set(nums)

        newHead = ListNode()
        newHead.next = head

        prev = newHead
        temp = head

        while temp:
            if temp.val not in blocked:
                prev.next = temp
                prev = prev.next
            temp = temp.next

        prev.next = None

        return newHead.next

Complexity

  • Time: $O(n)$
    We traverse the linked list once.

  • Space: $O(1)$
    Since we are not using any extra space except for a few variables.

And we are done.