检查两个链接列表是否合并。如果是这样，在哪里？

Question

这个问题可能很旧，但是我想不出答案。

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

条件：

1. 我们不知道长度
2. 我们应该只解析每个列表一次。

示例。" src="https://imgs.xnip.cn/cj/l/74/b1286118-4d8c-4361-bd84-f3220bba4708.png" />

Answer 1

如果

• “不允许修改”是指“您可以更改，但最终应将其还原”，并且
• 我们可以将列表重复 两次

以下算法将是解决方案。

首先，数字。假设第一个列表的长度为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

解决了问题。