检查两个链表是否相交，如果相交，找出交点的位置。

Question

这个问题可能有些老，但我想不出答案。

假设有两个不同长度的列表，在某一点 合并；我们如何知道它们的合并点在哪里？

条件：

1. 我们不知道长度
2. 我们只能遍历每个列表一次。

- rplusg

---

我非常确定，如果不修改列表，它是无法正常工作的。（或者将其复制到其他地方以避免仅解析一次的限制。） - Georg Schölly

可能就是这个意思。该死的面试官！呵呵 - Kyle Rosendo

我有一个有趣的提议...假设列表的公共尾部是无限长的。如何使用恒定的内存找到节点交集？ - Akusete

在不修改列表、使用计数器或进行超过O(N)次迭代的情况下，下面发布了一个解决方案。 - Pavel Radzivilovsky

一个使用golang编写的时间复杂度为O(n^2)和O(n)的示例，后者使用了一个集合： https://play.golang.org/p/XpK3D_p-oq - jpgerek

Answer 1

以下是我见过的最伟大的解决方案 - O(N)，无计数器。我在对候选人S.N.进行面试时从他那里得到了它，地点在VisionMap。

创建两个迭代指针，使其每次向前移动直到末尾，然后跳到相反列表的开头，如此往复。将两个指针分别指向两个链表头部。每次将每个指针向前移动1，直到它们相遇。这可能需要进行一次或两次操作。

我仍然在面试中使用这个问题，但是为了看看某人理解为什么这个解决方案有效需要多长时间。

- Pavel Radzivilovsky

---

太棒了！ - Cong Hui

这是一个好答案，但您必须两次遍历列表，这违反了条件＃2。 - tster

如果可以保证合并点存在，我认为这个解决方案非常优雅。但是如果没有检测到合并点，它将会无限循环，因此无法起作用。 - alternate direction

太棒了！解释：我们有两个列表：a-b-c-x-y-z 和 p-q-x-y-z。第一个指针的路径是 a,b,c,x,y,z,p,q,x，第二个指针的路径是 p,q,x,y,z,a,b,c,x。 - Nikolai Golub

很棒。对于那些不理解的人，请数一下从head1 -> tail1 -> head2 -> 相交点和从head2 -> tail2 -> head1 -> 相交点所经过的节点数量。两者将相等（绘制不同类型的链接列表以验证此内容）。原因是两个指针在到达相交点之前必须先行进相同的距离head1-> IP + head2->IP。因此，当它们到达IP时，两个指针将相等，并且我们找到了合并点。 - adev

Answer 2

Pavel的答案需要修改列表，并且需要对每个列表进行两次迭代。

这里有一个解决方案，只需要对每个列表进行两次迭代（第一次是计算它们的长度；如果已知长度，则只需要迭代一次）。

其思想是忽略较长列表的起始条目（合并点不能在那里），以使两个指针与列表末尾的距离相等。然后将它们向前移动，直到它们合并。

lenA = count(listA) //iterates list A
lenB = count(listB) //iterates list B

ptrA = listA
ptrB = listB

//now we adjust either ptrA or ptrB so that they are equally far from the end
while(lenA > lenB):
    ptrA = ptrA->next
    lenA--
while(lenB > lenA):
    prtB = ptrB->next
    lenB--

while(ptrA != NULL):
    if (ptrA == ptrB):
        return ptrA //found merge point
    ptrA = ptrA->next
    ptrB = ptrB->next

这个答案的时间复杂度与我的另一个答案是渐进相同的（线性时间），但可能有更小的常数，因此可能更快。但我认为我的另一个答案更酷。

- Artelius

---

+1 像这样，也不需要对列表进行任何修改，大多数链表实现通常提供长度。 - keshav84

我们有太多的Pavel了。我的解决方案不需要修改列表。 - Pavel Radzivilovsky

好的回答。但这个算法的时间复杂度是多少呢？是O(n + m)吗？其中n表示链表1中的节点数，m表示链表2中的节点数？ - Vihaan Verma

不需要同时移动两个列表中的指针：我们只需查看差值是否大于两条路径中较小的那个，如果是，则在较小的列表中按小值移动，否则在较小的列表中按差值+1的值移动；如果差值为0，则最后一个节点就是答案。 - Vishal Anand

事实上，这甚至可以用来计算是否存在合并点，因为一旦到达一个列表的末尾，我们只需存储末尾节点，并在另一个列表到达其末尾时进行比较。由于我们只创建了一个虚拟循环而不是真正的循环，所以这个方法非常有效。 - LionsAd

Answer 3

如果“不允许修改”的意思是“你可以做出更改，但最终它们应该被恢复”，并且我们可以精确遍历列表两次，那么以下算法将是解决方案。首先，考虑数字。假设第一个列表的长度为a+c，第二个列表的长度为b+c，其中c是它们共同的“尾部”（合并点后面）的长度。我们将它们表示如下：

x = a+c
y = b+c

因为我们不知道长度，所以我们将在没有额外迭代的情况下计算 x 和 y；你将会看到如何实现。

然后，我们遍历每个列表并在遍历时反转它们！如果两个迭代器同时到达合并点，那么我们只需比较它们即可找出该点。否则，一个指针将在另一个指针之前到达合并点。

之后，当另一个迭代器到达合并点时，它不会继续前往公共尾部。相反，它将返回先前到达合并点的列表的起始位置! 因此，在到达更改后的列表末端（即另一个列表的原始开头）之前，它将总共进行 a+b+1 次迭代。我们称其为 z+1。

首先到达合并点的指针将继续迭代，直到达到列表的结尾。它所做的迭代次数应计算，等于 x。

然后，该指针迭代回来，并再次反转列表。但是现在它不会回到它最初开始的列表的开头！相反，它将回到另一个列表的开头！它所做的迭代次数应计算，并等于 y。

因此，我们知道以下数字：

x = a+c
y = b+c
z = a+b

经过分析，我们得出结论：

a = (+x-y+z)/2
b = (-x+y+z)/2
c = (+x+y-z)/2

这解决了问题。

- P Shved

---

评论中指出不允许修改列表！ - Skizz

我喜欢这个答案（非常有创意）。 我唯一的问题是它假定您知道两个列表的长度。 - tster

@tster，@calvin，答案不假设，我们需要长度。它可以在行内计算。对我的答案进行解释。 - P Shved

@Forethinker 哈希访问过的节点和/或将其标记为已访问需要 O(列表长度) 的内存，而许多解决方案（包括我的，尽管它不完美且复杂）需要 O(1) 的内存。 - P Shved

受到如此简洁的回答启发 - Cong Hui

Answer 4

如果你知道它们将要合并：

假设你从以下内容开始：

A-->B-->C
        |
        V
1-->2-->3-->4-->5

1) 遍历第一个列表，将每个下一个指针设置为NULL。

现在你有：

A   B   C

1-->2-->3   4   5

2) 现在浏览第二个列表，等待直到您看到NULL，那就是合并点。

如果您不能确定它们是否合并，则可以为指针值使用哨兵值，但这不够优雅。

- tster

---

然而，在这个过程中你会破坏这个列表，以后就再也无法使用了:P - Kyle Rosendo

@Kyle Rozendo，好的，我的解决方案改变了列表，使它们可以在处理后恢复。但这更清晰地展示了概念。 - P Shved

我没有看到列表修改是不允许的。我会考虑一下，但是如果不存储每个节点，我脑海中就没有任何想法。 - tster

来吧，那是正确的答案！我们只需要调整一下问题 :) - P Shved

创建内存泄漏的优秀算法。 - Karoly Horvath

Answer 5

如果我们能够精确地迭代列表两次，那么我可以提供一种确定合并点的方法：

• 迭代两个列表并计算长度 A 和 B；
• 计算长度差 C = |A-B|；
• 同时开始迭代两个列表，但在较长的列表上额外向前走 C 步；
• 这两个指针将在合并点相遇。

- rachvela

Answer 6

这里有一个解决方案，计算速度很快（每个列表只迭代一次），但使用了大量内存：

for each item in list a
  push pointer to item onto stack_a

for each item in list b
  push pointer to item onto stack_b

while (stack_a top == stack_b top) // where top is the item to be popped next
  pop stack_a
  pop stack_b

// values at the top of each stack are the items prior to the merged item

- Skizz

---

这相当于对列表进行两次处理。 - Georg Schölly

我想从技术上讲，您正在两次使用列表进行操作，但这比Kyle Rozendo的解决方案有了显著的改进。现在，如果“处理列表”被定义为“读取链接值并跟随指针”，那么可以认为它只处理了一次列表-它会一次读取每个链接值，存储它们，然后进行比较。 - Skizz

肯定比我的快，毫无疑问。 - Kyle Rosendo

Answer 7

您可以使用一组Node。遍历一个列表并将每个Node添加到集合中。然后遍历第二个列表，对于每次迭代，请检查Node是否存在于集合中。如果存在，则找到了合并点 :)

- isyi

---

我担心（因为Ω(n)的额外空间），这是唯一的方法（而不是重建列表或多次解析列表）。对于第一个列表，检测循环很容易（检查节点是否在集合中）-在第二个列表上使用任何循环检测方法以确保终止。 （面试问题可能涉及仔细听取问题陈述，而不是立即使用您知道的工具来解决问题。） - greybeard

Answer 8

这可能违反了“仅解析每个列表一次”的条件，但实现乌龟和兔子算法（用于查找循环列表的合并点和周期长度），因此您可以从List A开始，在到达末尾的NULL时，假装它是指向List B开头的指针，从而创建循环列表的外观。然后，该算法将告诉您合并在List A下面多远（根据维基百科描述的变量'mu'）。另外，“lambda”值告诉您List B的长度，如果需要，您可以在算法过程中计算出List A的长度（当重定向NULL链接时）。

- Artelius

---

基本上就是我说的那样，只不过用了更高级的名称。 :P - Kyle Rosendo

完全不是。这个解决方案在操作上是O(n)，在内存使用上是O(1)（实际上只需要两个指针变量）。 - Artelius

是的，应该删除我之前的评论，因为我的解决方案有点改变了。呵呵。 - Kyle Rosendo

但我不明白这一开始怎么适用的？ - Artelius

你的解释是，而不是算法本身。也许我有不同的看法，但是嘿。 - Kyle Rosendo

你可能确实如此。但没关系。 - Artelius

Answer 9

也许我过于简化了，但只需迭代最小的列表并使用最后一个节点的链接作为合并点即可？

因此，当 Data->Link->Link == NULL 时是终点，将 Data->Link 作为合并点（在列表末尾）。

编辑：

好吧，从你发布的图片中可以看出，你首先解析两个列表，先处理最小的。对于最小的列表，您可以保留到以下节点的引用。现在，当您解析第二个列表时，您会比较引用以找到 Reference [i] 是 LinkedList[i]->Link 处的引用。这将给出合并点。现在用图片来解释一下（在 OP 的图片上叠加值）。

您有一个链表（下面显示引用）： A->B->C->D->E 您有第二个链表： 1->2-> 合并后的列表的引用如下所示： 1->2->D->E-> 因此，您将第一个“较小”的列表映射为已合并的列表（我们正在计算的合并列表的长度为4，而主列表为5）。

循环遍历第一个列表，保持引用的引用。

该列表将包含以下引用：Pointers { 1, 2, D, E }。

现在我们遍历第二个列表：

-> A - Contains reference in Pointers? No, move on
-> B - Contains reference in Pointers? No, move on
-> C - Contains reference in Pointers? No, move on
-> D - Contains reference in Pointers? Yes, merge point found, break.

当然，你可以维护一个新的指针列表，但这并不超出规范。然而，第一个列表只被解析一次，如果存在合并点，第二个列表将只被完全解析一次。否则，它会更早地结束（在合并点处）。

- Kyle Rosendo

---

虽然与我最初想说的略有不同，但从OP似乎想要的来看，这样做就可以了。 - Kyle Rosendo

现在更清楚了。但它在内存使用方面是线性的。我不喜欢这个。 - Artelius

什么？多线程是更好地利用处理能力的一种方式，而不是减少算法所需的总处理能力。而且说代码可以以任意数量的方式实现只是借口。 - Artelius

这真的让“仅解析每个列表一次”的限制接近破裂点。你所做的只是复制一个列表，然后检查另一个列表是否与副本相同。 - Skizz

嗯，是的和不是的。我并不是复制列表本身，只是它们的引用。所以至少开销并不完全相同，有点差别 :P - Kyle Rosendo

Answer 10

我在我的FC9 x86_64上测试了一个合并案例，并打印出每个节点的地址，如下所示：

Head A 0x7fffb2f3c4b0
0x214f010
0x214f030
0x214f050
0x214f070
0x214f090
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170


Head B 0x7fffb2f3c4a0
0x214f0b0
0x214f0d0
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170

请注意，由于我已经对节点结构进行了对齐，因此当使用malloc()分配节点时，地址会与16字节对齐，最后4位是0，即0x0或000b。 因此，如果您也处于相同的特殊情况（对齐的节点地址），则可以使用这些最后4位。 例如，在从头到尾遍历两个列表时，请设置访问节点地址的4位中的1或2位，即设置一个标志；

next_node = node->next;
node = (struct node*)((unsigned long)node | 0x1UL);

请注意，上述标志不会影响实际节点地址，而只会影响您保存的节点指针值。

一旦发现有人设置了标志位，则第一个找到的节点应该是合并点。完成后，您应该通过清除您设置的标志位来恢复节点地址。但重要的是，在迭代时（例如，node = node->next），您应该小心进行清理。记住您已经设置了标志位，所以要这样做。

real_node = (struct node*)((unsigned long)node) & ~0x1UL);
real_node = real_node->next;
node = real_node;

由于这个提案将恢复修改过的节点地址，因此可以被视为“无修改”。

- Test

---

+1，这是“仅迭代一次”自然而然想到的，不知道为什么从来没有得到赞同！很漂亮的解决方案。 - jman