Remove Duplicates from an Unsorted Linked List

Problem Statement

Given the head of an unsorted singly linked list, remove all nodes with duplicate values, keeping only the first occurrence of each value.

Example 1:

Input: 1 -> 2 -> 3 -> 2 -> 4 -> 1 -> null
Output: 1 -> 2 -> 3 -> 4 -> null

Example 2:

Input: 5 -> 5 -> 5 -> 5 -> null
Output: 5 -> null

Constraints:

• 0 <= list length <= 10^5.
• -10^5 <= Node.val <= 10^5.

Difficulty: Easy / Medium Round: OA

---

Pattern Recognition

• What is the input structure? An unsorted singly linked list.
• What are we optimizing? In-place removal, with O(1) per-node work ideally.
• What pattern does this fit? Hash set + single traversal. The hash set tracks seen values; you unlink any node whose value has appeared.
• Why does this pattern fit? With a hash set you get O(1) "have I seen this value?" lookups. Without extra space, you would need nested traversal (O(n^2)) or a modified list (e.g., sort first, destroying order).

---

Approach

Brute Force — Nested Scan

For each node, walk the remainder of the list and unlink any node with the same value.

Time: O(n^2). Space: O(1). Why this is the "no extra space" answer: If the problem explicitly forbids extra memory, this is the fallback. Otherwise, the hash set is strictly better.

Optimal — Hash Set + Single Pass

Key Insight: Record values in a set as you walk the list. When you find a node whose value is already in the set, unlink it by redirecting the previous node's next pointer.

Step-by-step:

1. If head is null, return null.
2. Insert head.val into the set.
3. Walk with a pointer cur starting at head.
4. While cur.next is not null:
   • If cur.next.val is already in the set, skip: cur.next = cur.next.next.
   • Else, insert cur.next.val into the set and advance cur = cur.next.
5. Return head.

Crucially, when you unlink cur.next, you do not advance cur — the new cur.next still needs to be checked.

Time: O(n). Space: O(n) for the set.

---

Walkthrough

Trace on 1 -> 2 -> 3 -> 2 -> 4 -> 1:

Initial: seen = {1}, cur = [1].

iter	cur.val	cur.next.val	in set?	action	list	seen
1	1	2	no	add 2, advance	1→2→3→2→4→1
2	2	3	no	add 3, advance	1→2→3→2→4→1
3	3	2	yes	skip (cur.next = 4 node)	1→2→3→4→1
4	3	4	no	add 4, advance	1→2→3→4→1
5	4	1	yes	skip (cur.next = null)	1→2→3→4
6	4	null	—	terminate

Answer: 1 -> 2 -> 3 -> 4.

---

Implementation

TypeScript

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(v: number = 0, n: ListNode | null = null) {
        this.val = v;
        this.next = n;
    }
}

function removeDuplicatesUnsorted(head: ListNode | null): ListNode | null {
    if (!head) return null;
    const seen = new Set<number>();
    seen.add(head.val);

    let cur = head;
    while (cur.next) {
        if (seen.has(cur.next.val)) {
            // Unlink duplicate; do NOT advance cur — new cur.next must be checked.
            cur.next = cur.next.next;
        } else {
            seen.add(cur.next.val);
            cur = cur.next;
        }
    }
    return head;
}

C++

#include <unordered_set>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int v) : val(v), next(nullptr) {}
};

ListNode* removeDuplicatesUnsorted(ListNode* head) {
    if (!head) return nullptr;
    std::unordered_set<int> seen;
    seen.insert(head->val);

    ListNode* cur = head;
    while (cur->next) {
        if (seen.count(cur->next->val)) {
            // Unlink duplicate.
            cur->next = cur->next->next;
        } else {
            seen.insert(cur->next->val);
            cur = cur->next;
        }
    }
    return head;
}

Watch out:

1. Advancing cur after deletion. If you advance, you skip checking the new cur.next, potentially leaving a duplicate in place.
2. Empty list. Return null immediately; otherwise the head.val access throws.
3. Memory management in C++. If the problem wants you to delete the unlinked nodes (to avoid leaks), remember to save the pointer before re-linking.

---

Complexity Analysis

	Time	Space
Brute Force (Nested Scan)	O(n^2)	O(1)
Optimal (Hash Set)	O(n)	O(n)

Bottleneck: You must visit every node. With a hash set, each visit is O(1) amortized.

---

Edge Cases

1. Empty list — return null.
2. Single node — no duplicates possible; return as-is.
3. All identical values — return a single node.
4. No duplicates — return the list unchanged.
5. Duplicates at the head — the initial seen.add(head.val) is what keeps the head from being incorrectly re-added. The head itself is never removed (it is always the first occurrence by definition).
6. Negative values — hash set handles them natively.

---

Related Problems

• LC 83 — Remove Duplicates from Sorted List — Sorted version; no hash set needed (compare adjacent).
• LC 82 — Remove Duplicates from Sorted List II — Remove all occurrences of any duplicated value. Harder, needs a dummy head and two pointers.
• LC 1836 — Remove Duplicates from an Unsorted Linked List — Closest match to this problem as stated on LeetCode Premium.

---

OA Strategy Notes

Quick warmup, 10-15 minutes. The only risk is the "do not advance cur after deletion" bug. Trace one case on paper before submitting. For OAs that forbid extra memory, mention the O(n^2) fallback and ask if the hash-set solution is acceptable.

---

What is Expected at Each Level

Junior: Writes the hash set solution; may forget the "don't advance after delete" rule and get a partial pass on tests.

Mid-level: Clean one-pass with correct deletion semantics. Discusses the O(n^2) no-extra-space alternative.

Senior: Brings up the follow-up variant (remove all occurrences, LC 82-style), discusses memory cleanup, and notes that a doubly-linked list would simplify the deletion logic.