求两个链表的交点? [英] Finding Intersection point of two linked list?
问题描述
Most of sites present this solution(see Method 3 at http://www.geeksforgeeks.org/write-a-function-to-get-the-intersection-point-of-two-linked-lists/ )
1)获取第一个列表中的节点数，让计数为c1.
1) Get count of the nodes in first list, let count be c1.
2)获取第二个列表中的节点数，让计数为c2.
2) Get count of the nodes in second list, let count be c2.
3)获得计数差d = abs(c1 – c2)
3) Get the difference of counts d = abs(c1 – c2)
4)现在遍历从第一个节点到d个节点的较大列表，因此从这里开始，两个列表的节点数均相等.
4) Now traverse the bigger list from the first node till d nodes so that from here onwards both the lists have equal no of nodes.
5)然后，我们可以并行遍历两个列表，直到遇到一个公共节点.(请注意，获取公共节点是通过比较节点的地址)
5) Then we can traverse both the lists in parallel till we come across a common node. (Note that getting a common node is done by comparing the address of the nodes)
我的理解是，如果第一个节点本身正在合并节点，则上述解决方案将无法工作.说list1有5个元素，list2有3个元素，其中element1是合并点.根据上述算法，差异计数为2.因此，我们首先遍历list1中的前2个节点.从列表中的3个元素开始，遍历元素毫不一一列出.所以我永远也不会得到合并点.不是吗?
My understanding is above solution wont work if first node itself is merging node. Say list1 has 5 elements and list2 has 3 elements where element1 is the merging point. As per above algo, difference count is 2. so first we will traverse the first 2 nodes in list1. starting from 3 elementin list, traverse element feom each list one by one. So i will never get the merging point. Is n't it?
我的建议解决方案:
1)遍历列表1.
2)将每个元素的内存地址(带有System.identitityHashMap)放入基于哈希的数据结构中
2) Put each element memory address(with System.identitityHashMap) in hash based data structure
3)遍历列表2.获取每个元素的内存地址，并查看其是否存在于哈希图中.如果是，则为合并点.
3)Traverse thru list2.Get the memory address of each element and see if its exist in hashmap. If yes its the merging point.
更新:-输入为
list1 = 1->3->5->6->7
list2 = 1->4->5
根据建议的解决方案，链接大小的差异为2.首先遍历list1中的3，然后比较 5->.6->7 和 1->4->5 .因此，此处缺少合并点1.
As per solution suggested in link difference in size is 2. First traverse up to 3 in list1, then compare 5 -> 6 -> 7 with 1 -> 4 -> 5. So merging point 1 is missed here.
推荐答案
我的理解是，如果第一个节点本身是上述解决方案将无法正常工作合并节点
My understanding is above solution wont work if first node itself is merging node
您的理解是错误的，只要方法可行即可.考虑您的示例:
Your understanding is incorrect, provided approach will work. Considering your example :
list1 = 1->2->3->4->5
list2 = 3->4->5 和节点 3 是交点.
差异d = 5-3 = 2，
the difference d = 5 - 3 = 2,
list1将被转发2，并指向 3->.4->5 ，因此它将指向与 list2 完全相同的节点，这将通过在第5步)进行的首次比较显示出来.
after step 4) list1 will be forwarded by 2 and will point to 3 -> 4 -> 5, so it will point to exactly same node as list2, which will be revealed by first comparison perfromed at step 5).
由于您是用Java实现的，因此要比较元素内存地址"(来自您的建议)，您只需比较引用，只有在引用(指向")同一对象时，引用才会相等.
Since you implement this in Java, to compare "element memory address" (from your proposal) you simply compare references, which will give you equality only if they refer ("point to") the same object.
希望有帮助.
这篇关于求两个链表的交点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
