面试题:判断两个链表是否连通
Intrerview question: determine whether two linked lists are connected or not
问题是:写一个布尔函数,接收两个链表,returns这两个链表是否相连(在某些时候它们都指向同一个节点)。我不允许分配任何内存,如地图,只能分配变量。他们希望它的线性时间复杂度为 o(n)。
我的方法是遍历一个链表并将每个节点与另一个链表中的所有节点进行比较,但其复杂度为 o(n^2) 并且不够好
这里有两点需要考虑:
您需要查找列表是否已连接。
那很简单。正如@user3386109 所指出的,只需检查最后一个节点是否相同并且 return 一个布尔值。
你也需要找到交点
在这里,找到两个列表的长度(让它们为 a
和 b
、a>b
)。遍历第一个列表中的a-b
个节点,然后开始逐个比较两个列表中的节点以找到交点。
这两种情况都可以在 O(N) 时间和 O(1) 时间内完成 space
问题是:写一个布尔函数,接收两个链表,returns这两个链表是否相连(在某些时候它们都指向同一个节点)。我不允许分配任何内存,如地图,只能分配变量。他们希望它的线性时间复杂度为 o(n)。 我的方法是遍历一个链表并将每个节点与另一个链表中的所有节点进行比较,但其复杂度为 o(n^2) 并且不够好
这里有两点需要考虑:
您需要查找列表是否已连接。
那很简单。正如@user3386109 所指出的,只需检查最后一个节点是否相同并且 return 一个布尔值。你也需要找到交点
在这里,找到两个列表的长度(让它们为a
和b
、a>b
)。遍历第一个列表中的a-b
个节点,然后开始逐个比较两个列表中的节点以找到交点。
这两种情况都可以在 O(N) 时间和 O(1) 时间内完成 space