从双链表中删除重复

Hello I stumbled following question You given unsorted doubly linked list.You should find and delete duplicates from Doubly linked list.

你好，我遇到了一个问题，你给我的是未排序的双向链表。您应该从双链表中查找并删除重复的内容。

What is the best way to do it with minimum algorithmic complexity?

用最小的算法复杂度做这件事最好的方法是什么?

Thank you.

谢谢你！

4 个解决方案

#1

If the space is abundance and you have to really optimize this with time, perhaps you can use a Hashset (or equivalent in C++). You read each element and push it to the hashset. If the hashset reports a duplicate, it means that there is a duplicate. You simply would delete that node.

如果空间足够大，并且您必须随着时间进行优化，那么您可以使用Hashset(或者在c++中等效)。您读取每个元素并将其推入hashset。如果hashset报告一个副本，则意味着有一个副本。您只需删除该节点。

The complexity is O(n)

复杂度是O(n)

#2

Think of it as two singly linked lists instead of one doubly linked list, with one set of links going first to last and another set going last to first. You can sort the second list with a merge sort, which will be O(n log n). Now traverse the list using the first link. For each node, check if (node.back)->key==node.key and if so remove it from the list. Restore the back pointer during this traversal so that the list is properly doubly linked again.

把它想象成两个单链表，而不是一个双链表，一组链接先到最后，另一组链接先到最后。您可以使用合并排序对第二个列表进行排序，它将是O(n log n)。现在使用第一个链接遍历列表。对于每个节点，检查if (node.back)->键==节点。键，如果是，从列表中删除它。在此遍历过程中恢复后指针，以便列表再次被正确地双链连接。

This isn't necessarily the fastest method, but it doesn't use any extra space.

这并不一定是最快的方法，但是它不使用任何额外的空间。

#3

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

假设潜在雇主相信c++库:

// 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);
}

#4

With minimum complexity? Simply traverse the list up to X times (where X is the number of items), starting at the head and then delete (and reassign pointers) down the list. O(n log n) (I believe) time at worse case, and really easy to code.

用最小的复杂性?只需遍历列表直到X次(其中X是项的数量)，从开头开始，然后删除(并重新分配指针)到列表下面。O(n log n)(我相信)情况更糟，而且很容易编码。

#1