Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A set gives fast membership checks for values to remove. Deleting a linked-list node means reconnecting its predecessor to its successor, but leading deletions need separate handling because they have no retained predecessor.

Approach

Build a set from nums. Advance head while its value belongs to that set. If the list becomes empty, return the empty head. Otherwise begin at the first retained node.

Inspect the node after the current node. If its value must be removed, bypass it by assigning current.next = current.next.next, keeping the current node in place to inspect the new successor. Otherwise advance to that successor.

Return the adjusted head. Keeping the predecessor stationary after a deletion handles consecutive removable nodes, including at the tail. Retained nodes are reused in their original order, with no need to allocate a replacement list.

# 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]:
        s = set(nums)

        while head and head.val in s: head = head.next
        if not head: return None

        curr = head

        while curr.next:
            if curr.next.val in s: curr.next = curr.next.next
            else: curr = curr.next

        return head

Complexity analysis

Let a = nums.length and l be the linked-list length. Time: O(a + l). Auxiliary space: O(a) for the deletion set.