Problem Detail: I was wondering how to remove duplicate values from a linked list in $mathcal{O}(nlg 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
- 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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/16160 Ask a Question Download Related Notes/Documents
