Remove Duplicates from an Unsorted Linked List

You are given an unsorted singly linked list. Your task is to remove all duplicate nodes from the list such that only the first occurrence of each element remains. The challenge requires you to design an algorithm that operates in linear time on average using additional data structures.

Note: The linked list is provided as a sequence of integer values. You need to construct the linked list, remove duplicates, and then output the modified list in order.

The removal should be performed in one pass, and you may assume that the list contains non-negative integers.

inputFormat

The first line of input contains a single integer n, the number of elements in the linked list. The second line contains n space-separated integers representing the node values of the linked list.

outputFormat

Output a single line containing the values of the modified linked list after all duplicates are removed. Print the remaining values as space-separated integers in the order they appear in the list.

4
1 2 3 4

1 2 3 4