检查两个链表是否在任何点合并的最佳可能算法？如果是的话,在哪里？

Question

可能重复:
链接列表面试问题

这是一个面试问题,我没有答案.给出两个列表,你不能改变列表,你不知道长度.提供最佳算法:

1. 检查两个列表是否在任何时候合并？
2. 如果合并,他们在什么时候合并？
3. 如果我允许您更改列表,您将如何修改算法？

Answer 1

我假设我们正在讨论简单的链表,我们可以安全地创建列表元素指针的哈希表.

Q1:迭代到两个列表的末尾,如果相应的最后一个元素相同,则列表在某个时刻合并.

复杂性 - O(N)空间复杂性 -O(1)

Q2:

1. 将一个列表的所有元素放入哈希表中
2. 迭代第二个列表,探测列表中每个元素的哈希表.第一个命中(如果有的话)是合并点,我们在第二个列表中有位置.
3. 要获取第一个列表中的位置,请再次遍历第一个列表,查找上一步中找到的元素.

时间复杂性 - O(N).空间复杂性 - O(N)

Q3:

1. 作为Q1,还要反转列表指针的方向.
2. 然后迭代反向列表,查找最后一个公共元素 - 即合并点 - 并将列表恢复为原始顺序.

时间复杂性 - O(N).空间复杂性 - O(1)