337. Remove Duplicates from Unsorted Linked List

Given the head of an unsorted singly linked list, remove all duplicate nodes so that each value appears only once. Preserve the relative order of first occurrences.

Use a hash set to track seen values in O(n) time.

Input: Head of an unsorted singly linked list.

Output: Head of the list with duplicates removed (first occurrence kept).

Examples

Input: [1,2,3,2,4,3,5]
Output: [1,2,3,4,5]
Explanation: Keep first occurrence of each value. Remove second 2 and second 3.

Input: [1,1,1,1]
Output: [1]
Explanation: All duplicates of 1 removed. Only first 1 kept.

Input: [1,2,3,4,5]
Output: [1,2,3,4,5]
Explanation: No duplicates. Return unchanged.

Constraints

• 0<=nodes<=10^4
• -10^9<=Node.val<=10^9

Asked by