如何查找两个链表是否相互交叉？

Question

可能重复：
Finding the intersecting node from two intersecting linked lists

鉴于两个大链表，这

1. 一）不要交叉

2. b）可以相交

   找到交点处的节点。通过路口我并不是指他们的价值观。我的意思是节点很常见。即来自列表A和列表B的两个不同节点指向相同节点

例如，

3->1->2->4->NULL 
    ^
     | 
5->4->3 

3->1->2->NULL 
    ^
     | 
9->2->3 

PS： 3.不允许使用哈希表。

1. 明显的蛮力方法N * M比较被排除。我们想要更好的解决方

Answer 1

要查找是否有交集，只需检查两个列表的“结尾”是否具有相同的地址。但这不是必须的。

将第一个列表通过从其最后一个节点链接到第一个[*]来将第一个列表变成循环。然后从第二个列表的开始处开始使用您最喜欢的循环寻找算法来查找循环及其起点。如果没有交集，则在第二个列表中找不到循环。如果你在第二个列表中找到一个循环，那么循环的开始点就是交点。

[*]如果您允许修改数据，请这样做。否则，写一个“步进”功能，对特定节点进行特殊处理。

Answer 2

如果列表相交，它们的最后一个节点是相同的