⚡Flashcard Drill➔
NeetCode #322LC-3217MediumLinked List
← Back to All Problems

#322 · #3217 · Delete Nodes From Linked List Present in Array(从链表中移除在数组中存在的节点)

📌 Problem Statement & Constraints

You are given the head of a linked list containing unique integers and an array nums. Remove all nodes whose value appears in nums and return the head. Constraints: 1 <= n <= 10^5, 1 <= nums.length <= 10^5, all values distinct.

💡 Core Algorithmic Approaches

  1. Put nums into a hash set for O(1) membership tests.
  2. Walk the list with a dummy head and unlink any node whose value is in the set.
  3. The dummy head handles removal of the original head.
  4. Unlinking without advancing is required, since the new successor has not been examined yet.

💻 Benchmark Python3 Implementation

class Solution:
    def modifiedList(self, nums: List[int], head: Optional[ListNode]) -> Optional[ListNode]:
        remove = set(nums)             # O(1) membership
        dummy = ListNode(0, head)
        cur = dummy
        while cur.next:
            if cur.next.val in remove:
                cur.next = cur.next.next   # unlink, do not advance
            else:
                cur = cur.next
        return dummy.next

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + m): building the set plus one pass over the list.
💾 Space Complexity
O(m) for the set.

⚠️ Interview Pitfalls & Follow-ups

  • Checking nums as a list: O(n * m) because each membership test is linear.
  • Advancing after unlinking: the new successor would be skipped.
  • Omitting the dummy head: removing the head would need a separate branch.
  • Returning head: the head may have been removed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems