Timeline for Removing duplicates from unsorted LinkedList
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 24, 2017 at 15:50 | comment | added | kyrill | How do you quicksort a linked list, with no random access? Will it really be \$O(n*log(n))\$? | |
| Apr 24, 2017 at 10:07 | comment | added | Emily L. | If you control the linked list class you could let each node have two additional pointers (sorted next and previous) you could then implement say quick sort on these pointers and use those to remove duplicates. Without affecting the original ordering :) you will use additional memory per node but it will probably be small in comparison to the size of T. | |
| Nov 23, 2014 at 22:35 | comment | added | janos | Good point! I updated my post to mention that. | |
| Nov 23, 2014 at 22:34 | history | edited | janos | CC BY-SA 3.0 |
added 397 characters in body
|
| Nov 23, 2014 at 0:22 | vote | accept | maniac87 | ||
| Nov 23, 2014 at 0:04 | vote | accept | maniac87 | ||
| Nov 23, 2014 at 0:04 | |||||
| Nov 22, 2014 at 23:40 | comment | added | maniac87 | Well another way is to sort the linkedList = O(nlogn) and then remove duplicates from sortedLinkedList = O(n) which is total O(nlogn) operation but this is not inplace algorithm . I guess you are right that without using external storage the complexity will be O(n2) | |
| Nov 22, 2014 at 23:24 | comment | added | janos | Ah ok that's what you meant by buffer... Without a map/set, there's no way around \$O(n^2)\$: you have to compare all elements against all other, unless there are other conditions you can benefit from, for example the list items being sorted. | |
| Nov 22, 2014 at 23:20 | comment | added | maniac87 | I know how to solve this in O(n) using external buffer but my question was how to make the solution efficient without using buffer . even though in the above code we dont compare each element with the rest of the elements but the complexity is still O(n2) | |
| Nov 22, 2014 at 23:12 | history | answered | janos | CC BY-SA 3.0 |