找到两个双向链表的交点

Question

我有一个作业，需要找到两个单链表的交集。我还需要找到两个双向链表的交集：

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

• 对于双向链表，我感到困惑：同样的方法可能有效，但我猜应该有更快的方法。

请问是否有更加高效的方法来查找两个双向链表的交集？我认为可能可以将它们合并并检查重复项，但我不确定这将如何运作以及其效率如何。

编辑：此处的“交集”指的是共享值，而不是共同节点。 编辑：实现应当在没有使用哈希的情况下完成。

- lalaland

---

如果两个双向链表共享任何节点，则它们是相同的，并且每个节点都相交。对于单向链表，如果它们相交，则它们共享相同的终端节点。测量两个列表的长度，沿着较长的列表移动，直到您与末尾等距离，然后移动锁步比较节点对。 - Dave

@Stef 对于歧义我感到抱歉。我在谈论重复内容。 - lalaland

这些值能否适应内存？您可以使用哈希表以线性时间和线性空间来解决。 - Dave

@lalaland：如果你不能使用哈希表，那么你用排序的方法可能是人们期望你采取的方式。当你完成项目后，你可以接受这个答案。 - chqrlie

@chqrlie 谢谢，我会这样做。 - lalaland

Answer 1

如果其中一个列表非常短或者明显比另一个列表短，那么使用复杂度为O(n*m)的简单嵌套线性扫描可能比对较长的列表进行排序更快。这是处理非常小的n或m（1或0）的最佳方法。

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

有一种可能更快的方法来查找两个列表的交集，单向或双向链接，或更一般地说是两个集合的交集，使用哈希表：

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

整体时间复杂度为O(n+m)，使用O(n)的额外空间。另一个优点是使用此方法不会修改列表，这可能是一项要求。

- chqrlie

---

将第一个列表中的每个项目放入一个集合中。对于第二个列表也是如此。取两个集合的交集。 - Marichyasana

@lalaland：如果其中一个列表非常短，则对小列表的每个元素使用简单的线性查找，否则对两个列表进行排序并并行扫描它们是一个不错的练习，也可能是您需要实现的内容。 - chqrlie

@lalaland: 我认为在这个练习中很难利用双向链表。对双向链表进行排序相当棘手，将其作为单向链表排序并在最后一次扫描中重建后向链接更简单。 - chqrlie

@chqrlie最后一个问题：数组或哈希表哪个是最佳选择？谢谢。 - lalaland

@lalaland：哈希表可以用于将元素查找的复杂度降至O(1)。如果将第二个列表的元素存储到已排序的数组中，则查找操作将需要O(log(m))，因此总复杂度变为O(m.log(m))来对第二个数组进行排序加上O(n.log(m))来查找第一个列表的元素，合并为O((n+m).log(m))，如果n远大于m，则略优于O(n.log(n))+O(m.log(m))。但请注意，对列表进行高效排序的方法是将元素复制到数组中，对数组进行排序，然后重新链接列表。 - chqrlie

Answer 2

我会扩展我的评论。

假设有两个双向链表相交。那么它们有一个共同的节点。从该节点开始沿着指针确定两个方向上的所有节点，因此这两个链表有所有节点都是相同的。

对于无环单向链表，如果它们至少有一个共同节点，则可以通过从该节点到末尾的指针来确定所有后续节点。这意味着我们可以通过测量链表的长度来找到公共节点，并使用两个指针比较距离末尾相等的节点，直到找到第一对相等的节点。这需要O(n)时间和O(1)空间。

如果存在（或可能存在）一个循环，请使用Floyd的循环查找算法（也需要O(n)时间和O(1)空间）来查找它。这两个链表共享循环。如果初始节点不在循环中，则像以前一样进行（从循环的等距位置开始）。

- Dave

---

你好@dave。感谢你的回答，但我说的是重复值，而不是共同的节点。对于这种歧义，我感到很抱歉。 - lalaland