d********n
发帖数: 191 | 1 应该是道老题了，不过后来跟朋友讨论时有些新情况。前几天面试考的，
【都是单向链表】
1.如何判断两个链表相交。
方法不少，遍历两个链表，看最后一个节点是不是相同。或者将其中一个表首尾相连，
看另一个表是不是有环（指针一个一次走一步，一个一次走两步两步，blablabla）
2. 如何找到相交的那个点？
方法也不少。reverse两个链表，从头开始走，走到某一个点不同时，上一个点就是交
点。或者两个链表依次入栈，一个个往外pop，然后比较，跟reverse类似
还有就是便利两个链表，得到长度m和n，然后得到长度差abs(m-n)，较长的链表先走
abs(m-n)这么多个点，然后两边一起走，第一个相同的就是交点。
问题来了，如果两个链表其中一个是有环的，应该怎么解决？特别是针对第一个问题。
见附图 |
P**********c
发帖数: 3417 | 2 可以对有环的那个先找到环的交点，然后分两段考虑？
【在 d********n 的大作中提到】
: 应该是道老题了，不过后来跟朋友讨论时有些新情况。前几天面试考的，
: 【都是单向链表】
: 1.如何判断两个链表相交。
: 方法不少，遍历两个链表，看最后一个节点是不是相同。或者将其中一个表首尾相连，
: 看另一个表是不是有环（指针一个一次走一步，一个一次走两步两步，blablabla）
: 2. 如何找到相交的那个点？
: 方法也不少。reverse两个链表，从头开始走，走到某一个点不同时，上一个点就是交
: 点。或者两个链表依次入栈，一个个往外pop，然后比较，跟reverse类似
: 还有就是便利两个链表，得到长度m和n，然后得到长度差abs(m-n)，较长的链表先走
: abs(m-n)这么多个点，然后两边一起走，第一个相同的就是交点。
|
W**********r
发帖数: 8927 | 3 我的答案：
if(用快慢指针从A的头出发测A是不是有环 == Yes) {
if (用快慢指针分别从A和B的头出发测是否相遇 == Yes) {
确认相交；
追上的一点肯定在环上，以此可以遍历环，再分别从A和B出发依次比较是不是在环上的话，最后可以确定分别的交点。
}
else {
确认不相交；
}
}
else {
if(用快慢指针从B的头出发测B是不是有环 == Yes) {
确认不相交；
}
else {
遍历两个链表，得到长度m和n，然后得到长度差abs(m-n)，较长的链表先走abs(m-n)这么多个点，然后两边一起走，第一个相同的就是交点。始终不同就没交点。
}
} |
b*******8
发帖数: 37364 | 4 分别对每个链表判断是否有环，有环则记录环的交点，无环则记录终点。
如俩链表一个环一个非环，则断然不交。
如两个都非环，则看终点相同与否。
如都有环，则从一个环的交点出发走一圈看能否到另一个环的交点（同时出发速递1和2
的快慢指针，追上时正好慢指针走完一圈）。 |
s******n
发帖数: 226 | |
s******n
发帖数: 226 | |
