Challenge 07: Deduplicating Linked Lists

Problem

Write code that removes duplicates from an unsorted linked list in O(N) time using a hash table.

Input

You will be given a series of integers in the following format:

N
INT_1 INT_2 ... INT_N

Each input list consists of two lines:

1. The first line consists of the N number of items in the list.

2. The second line consists of the N items in the list separated by spaces.

Output

For each input list, output the list of integers without any duplicates. You should maintain the order in which the numbers appear in the input.

Example

Given the following input:

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

Your program should output the following:

1
1 2
1 2 3 4

Requirements

Your solution must meet the following requirements:

1. You must create and utilize a custom linked list (ie. you cannot use std::list) to store the input.

2. You must implement a deduplicate function or method that removes duplicates from a linked list in O(n) time using a std::unordered_set.

Submission

To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Challenge 07 - TA assignment list.

$ cd path/to/repo                   # Go to your repository
$ git checkout master               # Make sure we are on master branch
$ git pull                          # Make sure we have changes for GitLab
$ git pull upstream master          # Fetch and merge upstream changes
$ git checkout -b challenge07       # Create challenge07 branch
...                                 # Do your work
$ git commit                        # Commit your work (can do this multiple times)
$ git push -u origin challenge07    # Push branch to GitLab