Remove duplicates from an unsorted linked list
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: []
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²).