NeetCode #339LC-1836MediumLinked List
← Back to All Problems#339 · #1836 · Remove Duplicates From an Unsorted Linked List(从未排序的链表中移除重复元素)
📌 Problem Statement & Constraints
Given the head of an unsorted linked list, remove all nodes that have duplicate values, keeping only the distinct values, and return the head. Constraints:
1 <= n <= 10^5, 1 <= Node.val <= 10^4.💡 Core Algorithmic Approaches
- Count the frequency of every value in one pass.
- Then walk the list again with a dummy head, keeping only nodes whose value has frequency 1.
- The dummy head handles removal of the original head.
- Two passes, O(n) time and O(k) space for the counts.
💻 Benchmark Python3 Implementation
class Solution:
def deleteDuplicatesUnsorted(self, head: Optional[ListNode]) -> Optional[ListNode]:
from collections import Counter
cnt = Counter()
cur = head
while cur:
cnt[cur.val] += 1
cur = cur.next
dummy = ListNode(0, head)
prev = dummy
cur = head
while cur:
if cnt[cur.val] > 1: # duplicated -> drop
prev.next = cur.next
else:
prev = cur
cur = cur.next
return dummy.next⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): two passes.
💾 Space Complexity
O(k) for the counter, where k is the number of distinct values.
⚠️ Interview Pitfalls & Follow-ups
- Trying to do it in one pass: a node's status depends on the whole list, so the count must be complete first.
- Advancing
prevafter unlinking:prevmust stay put so the new successor is examined. - Forgetting the dummy head: removing the head would need a special case.
- Assuming the list is sorted: the unsorted case is exactly why a hash-based count is needed instead of an adjacent comparison.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.