399. Remove Duplicates from an Unsorted Linked List in O(n)

Given an unsorted linked list, remove all duplicate values so that each value appears only once, keeping the first occurrence of each value in its original order. Achieve O(n) time using a hash set. Return the resulting list as an array.

Input: An array of node values.

Output: Array — the de-duplicated list.

Examples

Input: [1,2,1,3,2,4]
Output: [1,2,3,4]
Explanation: First occurrences kept.

Input: [1,1,1,1]
Output: [1]
Explanation: All but one removed.

Input: [1,2,3]
Output: [1,2,3]
Explanation: No duplicates.

Constraints

• 0<=n<=10^5
• 0<=value<=10^9

Asked by