从两个相交链表中寻找相交节点 [英] Finding the intersecting node from two intersecting linked lists
问题描述
假设有两个单链表，它们在某个点相交并成为一个单链表.
Suppose there are two singly linked lists both of which intersect at some point and become a single linked list.
两个链表的头指针或起始指针都是已知的，但相交节点是未知的.此外，每个列表中的节点在它们相交之前的数量是未知的，并且两个列表可能都不同，即 List1 在到达交点之前可能有 n 个节点，List2 在到达交点之前可能有 m 个节点，其中 m 和 n 可能是
The head or start pointers of both the lists are known, but the intersecting node is not known. Also, the number of nodes in each of the list before they intersect are unknown and both list may have it different i.e. List1 may have n nodes before it reaches intersection point and List2 might have m nodes before it reaches intersection point where m and n may be
- m = n,
- m
- m > n
一个已知或简单的解决方案是将第一个列表中的每个节点指针与第二个列表中的每个其他节点指针进行比较，通过匹配的节点指针将我们引导到相交节点.但是，这种情况下的时间复杂度为 O(n2)，会很高.
One known or easy solution is to compare every node pointer in the first list with every other node pointer in the second list by which the matching node pointers will lead us to the intersecting node. But, the time complexity in this case will O(n2) which will be high.
找到相交节点的最有效方法是什么?
What is the most efficient way of finding the intersecting node?
推荐答案
这需要 O(M+N) 时间和 O(1) 空间，其中 M 和 N 是链表的总长度.如果公共部分很长(即 M,N >> m,n)，则可能效率低下
This takes O(M+N) time and O(1) space, where M and N are the total length of the linked lists. Maybe inefficient if the common part is very long (i.e. M,N >> m,n)
- 遍历两个链表，找到M和N.
- 回到头部，然后遍历 |M −N|较长列表中的节点.
- 现在进入锁定步骤并比较节点，直到找到共同的节点.
<小时>
查看更多这里.
这篇关于从两个相交链表中寻找相交节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
