Remove duplicates from double list

Question

Hi I stumbled upon the following question. You have specified an unsorted doubly linked list. You must find and remove duplicates from the Doubly linked list.

What is the best way to do this with minimal algorithmic complexity?

Thanks.

Answer 1

If space is abundance, and you should really optimize it over time, perhaps you can use a Hashset (or equivalent in C ++). You read each item and click on the hash. If the hash reports a duplicate, it means that there is a duplicate. You just delete this node.

Difficulty O(n)

Answer 2

Think of it as two lists linked together, rather than one doubly linked list, with one set of links being the first and the second the last. You can sort the second list with merge sort, which will be O (n log n). Now go through the list using the first link. For each node, check if there is (node.back)->key==node.key , and if you remove it from the list. Restore the back pointer during this crawl so that the list is correctly double-bound.

This is not necessarily the fastest method, but it does not use extra space.

Answer 3

Assuming the potential employer believes in the C ++ library:

 // untested O(n*log(n)) temlate <class T> void DeDup(std::list<T>& l) { std::set<T> s(l.begin(), l.end()); std::list<T>(s.begin(), s.end()).swap(l); } 

Answer 4

With minimal difficulty? Just move the list up to X times (where X is the number of elements) starting from the head, and then delete (and reassign the pointers) down the list. O (n log n) (I think) is the worst case time, and very easy to code.