由两个相交的链表寻找交叉点 [英] 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个节点之前到达交叉点和列表2可能具有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＆LT; n或
- M> N
一个已知或简单的解决方案是每一个节点指针中的第一个列表进行比较，在第二个列表中的匹配节点指针将导致我们的相交节点所有其他节点的指针。但是，在这种情况下，时间复杂度会为O（n 2 ），这将是高的。
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 |较长的列表上的节点。
- 现在，走在锁步和比较节点，直到你找到了常见的。
编辑：见<一href="http://richardhartersworld.com/cri/2008/linkedlist.html">http://richardhartersworld.com/cri/2008/linkedlist.html
这篇关于由两个相交的链表寻找交叉点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
