从双向链表中删除重复项

Question

Hello我磕磕绊绊地回答了以下问题你给出了未排序的双链表。您应该从双向链表中找到并删除重复项。

以最小的算法复杂性做到这一点的最佳方法是什么？

谢谢。

Answer 1

如果空间充足，并且您必须随着时间的推移真正优化它，也许您可以使用Hashset（或C++中的等效物）。您读取每个元素并将其推送到哈希集。如果哈希集报告重复，则表示存在重复。您只需删除该节点即可。

复杂性是O(n)

Answer 2

把它想象成两个单链表，而不是一个双向链表，一组链接从头到尾，另一组从最后到第一。您可以使用合并排序对第二个列表进行排序，该排序将是 O（n log n）。现在使用第一个链接遍历列表。对于每个节点，检查是否(node.back)->key==node.key，如果是，请将其从列表中删除。在此遍历期间恢复后退指针，以便再次正确双链接列表。

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

Answer 3

假设潜在雇主相信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);
}

Answer 4

复杂性最小？只需从头部开始遍历列表最多 X 次（其中 X 是项目数），然后删除（并重新分配指针）列表。O（n log n）（我相信）时间在更糟糕的情况下，而且真的很容易编码。