检查两个链表是否合并.如果有，在哪里? [英] 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?
条件:
- 我们不知道长度
- 我们应该只解析每个列表一次.
推荐答案
If
- 不允许修改"的意思是您可以更改，但最终它们应该被恢复"，并且
- 我们可以精确地迭代列表两次
以下算法将是解决方案.
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和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.
所以我们知道以下数字:
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屋！
