检查两个链表是否合并。如果是，在哪里？ [英] Check if two linked lists merge. If so, where?
问题描述
这个问题可能是老的，但我想不出一个答案。
This question may be old, but I couldn't think of an answer.
说，有两个不同长度的列表，点;我们如何知道合并点在哪里？
Say, there are two lists of different lengths, merging at a point; how do we know where the merging point is?
条件：
- 我们不知道长度
- 我们应该只解析每个列表一次。
推荐答案
如果
- 通过修改不允许，这意味着你可能会改变，但最终应该是恢复，而
- 我们可以遍历两次
- by "modification is not allowed" it was meant "you may change but in the end they should be restored", and
- we could iterate the lists exactly twice
以下算法将是解决方案。
the following algorithm would be the solution.
首先，数字。假设第一个列表的长度为 a + c ，第二个列表的长度为 b + c ，其中 c 是他们常用的尾（在合并点之后）的长度。我们来表示如下：
First, the numbers. Assume the first list is of length a+c and the second one is of length b+c, where c is the length of their common "tail" (after the mergepoint). Let's denote them as follows:
x = a+c
y = b+c
由于我们不知道长度，我们将计算 x code> y 无需额外的迭代;你会看到如何。
Since we don't know the length, we will calculate x and y without additional iterations; you'll see how.
然后，我们迭代每个列表，并在迭代时反转它们！如果两个迭代器同时到达合并点，那么我们只需比较就可以找到它。否则，一个指针将在另一个指针之前到达合并点。
Then, we iterate each list and reverse them while iterating! If both iterators reach the merge point at the same time, then we find it out by mere comparing. Otherwise, one pointer will reach the merge point before the other one.
之后，当另一个迭代器到达合并点时，它将不会进入公共尾。相反会回到之前已经达到合并点的列表的前一个！因此，在到达更改的列表（即其他列表的前一个开始）之前，他将使 a + b + 1 迭代总数。让我们称之为 z + 1 。
After that, when the other iterator reaches the merge point, it won't proceed to the common tail. Instead will go back to the former beginning of the list that had reached merge-point before! So, before it reaches the end of the changed list (i.e. the former beginning of the other list), he will make a+b+1 iterations total. Let's call it z+1.
首先到达合并点的指针将保持迭代，直到到达列表的末尾。应该计算它的迭代次数，并等于 x 。
The pointer that reached the merge-point first, will keep iterating, until reaches the end of the list. The number of iterations it made should be calculated and is equal to x.
然后，这个指针反复回放，再次反转列表。但现在它不会回到最初从它开始列表的开头！相反，它将转到其他列表的开头！应该计算其迭代次数，并等于 y 。
Then, this pointer iterates back and reverses the lists again. But now it won't go back to the beginning of the list it originally started from! Instead, it will go to the beginning of the other list! The number of iterations it made should be calculated and equal to y.
所以我们知道以下数字： / p>
So we know the following numbers:
x = a+c
y = b+c
z = a+b
从中我们确定
a = (+x-y+z)/2
b = (-x+y+z)/2
c = (+x+y-z)/2
哪个可以解决问题。
这篇关于检查两个链表是否合并。如果是，在哪里？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
