检查两个链表合并。如果是这样，在哪里？ [英] 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?
条件：
- 我们不知道的长度
- 我们应该分析每个列表只有一次。
推荐答案
如果
- 将改装是不允许的，它的意思，你可能会改变，但最终他们应该恢复，和
- 我们可以准确地遍历表的两次的
下面的算法将是解决办法。
the following algorithm would be the solution.
首先，号码。假设第一个列表长度 A + C ，第二个是长度 B + C ，其中ç是他们共同的尾巴的长度（的MergePoint后）。让我们表示他们如下：
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 和是无需额外的迭代;您将看到如何。
Since we don't know the length, we will calculate x and y without additional iterations; you'll see how.
然后，我们遍历每个列表和扭转他们，而迭代！如果这两个迭代器到达的同时并入点，那么我们发现它由单纯的比较。否则，1指针将在另一个之前到达合并点
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.
然后，该指针迭代返回并再次反转列表。但现在不会再回到列表它最初是从开始的开始！相反，它会去其他列表的开始！迭代它所做的数量应计算并等于是。
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.
因此，我们知道以下数字：
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
其中解决了这个问题。
Which solves the problem.
这篇关于检查两个链表合并。如果是这样，在哪里？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
