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?

  • $\begingroup$ Could you define what you mean by "purge"? $\endgroup$ – D.W. Oct 18 '13 at 17:57
  • $\begingroup$ @D.W. Probably corrected now. If not, hopefully the OP will clarify. $\endgroup$ – Juho Oct 18 '13 at 21:14
  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.

| cite | improve this answer | |
  • $\begingroup$ For example, one can easily use Mergesort for the first step. $\endgroup$ – Juho Oct 17 '13 at 14:23
  • $\begingroup$ If we use merge sort, I think we don't need the latter $O(n)$ processing, am I right? $\endgroup$ – Hadi Amiri Oct 17 '13 at 15:56
  • $\begingroup$ Yes, the modification of the merge sort, that you described in the question will also work for linked list. $\endgroup$ – Anton Oct 17 '13 at 18:57

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)$.

| cite | improve this answer | |
  • $\begingroup$ really cool, I wonder why I miss the hash table most of the times! but what if we are said that we can use no extra space except $O(1)$ space? $\endgroup$ – Hadi Amiri Oct 17 '13 at 15:55
  • $\begingroup$ @HadiAmiri, I do not understand your question. Your input is a linked list, not an array. How do you sort a linked list without putting its element into an array? Moreover, MergeSort does NOT sort in place!!! MergeSort requires more than additional $O(1)$ space owing to the internal "merge" function!!! $\endgroup$ – Massimo Cafaro Oct 17 '13 at 16:16
  • $\begingroup$ Forgetit, I was wrong! $\endgroup$ – Hadi Amiri Oct 19 '13 at 11:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.