algorithm - 面试题: determine whether two linked lists are connected or not

Question

问题是:编写一个 bool 函数，接收两个链表，并返回链表是否相连(在某个点上它们都指向同一个节点)。我不允许分配任何内存，如 map ，只能分配变量。他们希望它的线性时间复杂度为 o(n)。我的方法是遍历一个链表并将每个节点与另一个链表中的所有节点进行比较，但其复杂度为 o(n^2) 并且不够好

Answer 1

这里有两点需要考虑:

1. 您需要查找列表是否已连接。
   那很简单。正如@user3386109 所指出的，只需检查最后一个节点是否相同并返回一个 bool 值。

2. 你还需要找到交点。
   在这里，找到两个列表的长度(假设它们是 a 和 b，a>b)。遍历第一个列表中的a-b节点，然后开始逐个比较两个列表中的节点以找到交点。

两种情况都可以在O(N)时间和O(1)空间内完成