Problem statement

You are given the head of a singly linked list whose values are in no particular order. Remove every node whose value has already appeared earlier in the list, so that only the first occurrence of each value remains, and return the head. The surviving nodes keep their original order.

Example 1

Input: head = [5,2,2,4]
Output: [5,2,4]

Example 2

Input: head = [2,2,2,2,2]
Output: [2]

Example 3

Input: head = [3,1,3,2,1,4]
Output: [3,1,2,4]
Explanation: The second 3 and the second 1 are dropped; the first copies stay where they were.

Constraints

• 1 <= number of nodes <= 10^6
• 0 <= Node.val <= 10^6

Hints for Remove Duplicates from an Unsorted Linked List

1. Hint 1

   Unlike a sorted list, copies of a value need not be next to each other.

2. Hint 2

   Remember every value you have already kept — a hash set answers 'seen before?' in O(1).

3. Hint 3

   Walk with a pointer to the last kept node; if the next node's value is in the set, unlink it, otherwise add the value and move on.

How to solve Remove Duplicates from an Unsorted Linked List

Scan once, keeping a set of the values kept so far. A node whose value is in the set is a later copy and gets unlinked; otherwise its value joins the set. Unlinking from the previous kept node preserves the order of the rest.

Approach

1. Put head.val in a set and set prev = head.
2. While prev.next exists: if its value is in the set, skip it with prev.next = prev.next.next; otherwise add the value and set prev = prev.next.
3. Return head (the first node is always kept).

Why it works

When a node is examined, the set holds exactly the values of the nodes kept before it, which are the values that have appeared earlier (every earlier copy shares a value with a kept node). So a node is removed precisely when its value appeared earlier.

Complexity

• Time — O(n) expected
• Space — O(d) for the d distinct values

Pitfalls

• Sorting the list first would change the order of the survivors.
• Comparing each node with every earlier node is O(n²) — too slow for 10^6 nodes.
• After unlinking, stay on prev: the new next node must be checked as well.

Reference solution

Python

from typing import Optional

def removeDuplicates(head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None:
        return None
    seen = {head.val}
    prev = head
    while prev.next:
        if prev.next.val in seen:
            prev.next = prev.next.next
        else:
            seen.add(prev.next.val)
            prev = prev.next
    return head

Java

public static ListNode removeDuplicates(ListNode head) {
    if (head == null) return null;
    Set<Integer> seen = new HashSet<>();
    seen.add(head.val);
    ListNode prev = head;
    while (prev.next != null) {
        if (seen.contains(prev.next.val)) prev.next = prev.next.next;
        else { seen.add(prev.next.val); prev = prev.next; }
    }
    return head;
}

C++

ListNode* removeDuplicates(ListNode* head) {
    if (!head) return nullptr;
    unordered_set<int> seen{head->val};
    ListNode* prev = head;
    while (prev->next) {
        if (seen.count(prev->next->val)) prev->next = prev->next->next;
        else { seen.insert(prev->next->val); prev = prev->next; }
    }
    return head;
}

JavaScript

var removeDuplicates = function(head) {
    if (head === null) return null;
    var seen = new Set([head.val]);
    var prev = head;
    while (prev.next !== null) {
        if (seen.has(prev.next.val)) prev.next = prev.next.next;
        else { seen.add(prev.next.val); prev = prev.next; }
    }
    return head;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Design HashSet Easy
• Two Sum IV - Input is a BST Easy
• Check if Any Element Has Prime Frequency Easy