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$
$\endgroup$
2
-
$\begingroup$ Could you define what you mean by "purge"? $\endgroup$– D.W. ♦Oct 18, 2013 at 17:57
-
$\begingroup$ @D.W. Probably corrected now. If not, hopefully the OP will clarify. $\endgroup$– JuhoOct 18, 2013 at 21:14
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
- Sort the linked list in $O(n \log n)$ time.
- 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.
-
$\begingroup$ For example, one can easily use Mergesort for the first step. $\endgroup$– JuhoOct 17, 2013 at 14:23
-
$\begingroup$ If we use merge sort, I think we don't need the latter $O(n)$ processing, am I right? $\endgroup$ Oct 17, 2013 at 15:56
-
$\begingroup$ Yes, the modification of the merge sort, that you described in the question will also work for linked list. $\endgroup$– AntonOct 17, 2013 at 18:57
$\begingroup$
$\endgroup$
3
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)$.
-
$\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$ Oct 17, 2013 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$ Oct 17, 2013 at 16:16
-