How to purge a linked list in $\mathcal{O}(n\log n)$ time?

Question

I was wondering how to remove duplicate values from a linked list in $\mathcal{O}(n\lg n)$ time. I have an idea that by using merge sort when we want to compare elements for choosing the small one, if they are equal advance on pointer and just consider one element. Any alternatives?

Answer 1

1. Sort the linked list in $O(n \log n)$ time.
2. Go through each element of the list in their order and remove the element, if it is the same as the previous one in $O(n)$ time.

The total complexity is $O(n \log n)$, which is what you are searching for.

Answer 2

You can do it in $O(n)$ as follows.

1) Build an hash table by traversing the linked list and adding its elements to the hash table. In each iteration, search the hash table for the current element being considered in the iteration. If the element is not found, add to the hash table the element value as the key, and 1 as the corresponding value. If you instead find the element (which has been inserted in a previous iteration), you simply add 1 to the corresponding value and update the hash table entry (correctly updating the element multiplicity). At the end, your hash table will contain at most $n$ entries (this corresponds to the case that the element in the linked list are distinct), or less than $n$ elements, with at least one of the entries showing a multiplicity greater than one. This takes $O(n)$ time since in each of the $n$ iterations the work done on the hash table is $O(1)$.

2) Now, traverse the hash table and build a new linked list by adding a node for each element found. this takes at most $O(n)$ since the hash table contains at most $n$ elements, the work done on each element of the hash table is $O(1)$ and adding a node to the new list takes $O(1)$.

Therefore, the total complexity is at most $O(n)$.