⚡Flashcard Drill➔
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

  1. Count the frequency of every value in one pass.
  2. Then walk the list again with a dummy head, keeping only nodes whose value has frequency 1.
  3. The dummy head handles removal of the original head.
  4. 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 prev after unlinking: prev must 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.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems