Remove duplicates from an unsorted linked list

Easy

Problem

Given an unsorted linked list, keep the first occurrence of each value and delete later duplicates.

Example 1

Input:  5 → 2 → 2 → 4 → 5
Output: 5 → 2 → 4

Also asked as: Remove Duplicates in a Un-sorted Linked List

Test cases

Case 1

Input:    [5,2,2,4,5]
Expected: [5,2,4]

Case 2

Input:    [1,1,1]
Expected: [1]

Case 3

Input:    [3,1,2]
Expected: [3,1,2]

Case 4

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Hash set of seen values

Time O(n)Space O(n)

Keep a set; unlink any node whose value was already seen.

function dedupeUnsorted(head) {
const seen = new Set();
let prev = null, cur = head;
while (cur) {
if (seen.has(cur.val)) prev.next = cur.next;
else { seen.add(cur.val); prev = cur; }
cur = cur.next;
}
return head;
}

Without extra space: for each node, run an inner loop deleting later matches — O(n²).