algorithm - 检查两个链表是否合并。如果有，在哪里？

Question

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

比如说，有两个不同长度的列表，在一点合并；我们怎么知道合并点在哪里？

条件:

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

Answer 1

以下是迄今为止我所见过的最伟大的 - O(N)，没有计数器。我在面试候选人 S.N. 时得到了它。在 VisionMap .

像这样创建一个交互指针:它每次都向前移动直到结束，然后跳转到相反列表的开头，依此类推。 创建其中两个，指向两个头。 每次都将每个指针向前推进 1，直到它们相遇。这将在一次或两次通过后发生。

我仍然在采访中使用这个问题 - 但要看看人们需要多长时间才能理解为什么这个解决方案有效。