d********n 发帖数: 191 | 1 应该是道老题了,不过后来跟朋友讨论时有些新情况。前几天面试考的,
【都是单向链表】
1.如何判断两个链表相交。
方法不少,遍历两个链表,看最后一个节点是不是相同。或者将其中一个表首尾相连,
看另一个表是不是有环(指针一个一次走一步,一个一次走两步两步,blablabla)
2. 如何找到相交的那个点?
方法也不少。reverse两个链表,从头开始走,走到某一个点不同时,上一个点就是交
点。或者两个链表依次入栈,一个个往外pop,然后比较,跟reverse类似
还有就是便利两个链表,得到长度m和n,然后得到长度差abs(m-n),较长的链表先走
abs(m-n)这么多个点,然后两边一起走,第一个相同的就是交点。
问题来了,如果两个链表其中一个是有环的,应该怎么解决?特别是针对第一个问题。
见附图 |
P**********c 发帖数: 3417 | 2 可以对有环的那个先找到环的交点,然后分两段考虑?
【在 d********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 应该是道老题了,不过后来跟朋友讨论时有些新情况。前几天面试考的, : 【都是单向链表】 : 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 | |