list - 找到 2 个双向链表的交集

Question

我有一个任务，我需要找到 2 个单链接(单对单)列表的交集。我还必须为 2 个双向链接(双重 vs 双重)列表执行此操作:

• 对于单链表，我使用 mergeSort() 对两个列表进行排序，然后逐项比较 ==> O(m.log(m) + n。日志(n))

• 我对双向链表感到困惑:同样可以工作，但我想可能有更快的方法。

有人可以告诉我是否有更有效的方法来找到 2 个双向链表的交集？我想也许我们可以合并它们并检查重复项，但我不确定这将如何工作以及效率如何。

编辑:请注意，此处的“交叉点”表示共享值，而不是公共(public)节点。 编辑:实现应该在不使用散列的情况下完成

Answer 1

如果其中一个列表非常短或比另一个短得多，则复杂度为 O(n*m) 的简单嵌套线性扫描可能比对较长列表进行排序更快。对于非常小的 n 或 m(1 或 0)，这是最好的方法。

对于一般情况，您不能假设列表没有重复项，因此合并列表没有帮助。

使用哈希表查找 2 个列表的交集(单链接或双链接)或更一般的 2 个集合的交集可能是一种更快的方法:

• 创建一个可以保存重复项的空哈希表；
• 枚举第一个列表，将每个元素插入到哈希表中:O(n);
• 枚举第二个列表，对于每个元素，如果在哈希表中找到，则将其添加到交集并从哈希表中删除:O(m);
• 丢弃哈希表。

总体时间复杂度为 O(n+m)，使用了 O(n) 额外空间。一个额外的好处是列表不会用这种方法修改，这可能是一个要求。