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
- Put
numsinto a hash set for O(1) membership tests. - Walk the list with a dummy head and unlink any node whose value is in the set.
- The dummy head handles removal of the original head.
- 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
numsas 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.