I need to write a C++ that removes duplicates from an unsorted linked list in O(N) time using a hash table.

Each input list consists of two lines: The first line consists of the N number of items in the list. The second line consists of the N items in the list separated by spaces.

For each input list, I need to output the list of integers without any duplicates. The order in which the numbers appear in the input must be maintained.

For example...

Given the following input:

1 1 3 1 2 1 5 1 2 1 3 4

program should output the following:

1 1 2 1 2 3 4

I must create and utilize a custom linked list to store the input.

I must implement a deduplicate function or method that removes duplicates from a linked list in O(n) time using a std::unordered_set in some meaningful way(a way that using a hash table would give you some advantage, possibly in complexity).