Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
Problem Detail: 

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?

Asked By : Hadi Amiri

Answered By : Anton

  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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16160

 Ask a Question

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback