Remove Duplicates From an Unsorted Linked List

Remove Duplicates From an Unsorted Linked List

What is this problem about?

The Remove Duplicates From an Unsorted Linked List interview question asks you to clean up a singly linked list where nodes may appear in any order and duplicate values may be scattered throughout. Your task is to traverse the list and delete all nodes whose values have already appeared earlier in the list, keeping only the first occurrence of each value.

Why is this asked in interviews?

Microsoft and Amazon ask this problem to evaluate a candidate's proficiency with linked list traversal and auxiliary data structure selection. Unlike the sorted duplicate removal problem, you cannot rely on order — you need an O(n) extra space hash table to track seen values. It tests whether candidates understand the tradeoff between time and space and can cleanly manipulate node pointers without losing list integrity.

Algorithmic pattern used

The pattern is linked list traversal with a hash table for deduplication. Use a prev pointer and a curr pointer. Maintain a set of seen values. For each node: if the value is already in the set, update prev.next to skip curr (effectively removing curr). If not, add the value to the set and advance prev. Always advance curr. This achieves O(n) time and O(n) space.

Example explanation

List: 3 → 1 → 4 → 1 → 3 → 5

• 3: not seen → add to set, move prev and curr.
• 1: not seen → add to set.
• 4: not seen → add to set.
• 1: already seen → prev.next = curr.next (skip this node).
• 3: already seen → skip.
• 5: not seen → add to set.

Result: 3 → 1 → 4 → 5.

Common mistakes candidates make

• Advancing prev even when a node is removed — this breaks the linked list.
• Forgetting to handle edge cases like an empty list or a single-node list.
• Using a list instead of a set for tracking seen values, leading to O(n^2) time.
• Not handling the case where the head itself is a duplicate of a later node — but since we keep the first occurrence, head is always kept.

Interview preparation tip

For the Remove Duplicates From an Unsorted Linked List coding problem, the linked list and hash table interview pattern is fundamental. Practice distinguishing the prev and curr pointer updates carefully: prev only moves when a node is kept, not when it's deleted. Drawing the pointer diagram on paper before coding will save you from pointer bugs. This is a go-to warm-up problem at Microsoft for linked list rounds.