力扣——环形链表 II
题目链接：链接
题目描述：
https://i-blog.csdnimg.cn/direct/eeb7d06d7a6342368bd7bb6f9053dc80.png
思路：
我们知道用快慢指针遍历环形链表，两个指针肯定会相遇
如果从相同的出发点出发，快指针每次走两步，慢指针走一步，
https://i-blog.csdnimg.cn/direct/55eef4fbc4b84f609b8ea30a16905918.png
相同的时间内，快指针的旅程是慢指针的两倍
当他们相遇时，快指针已经在环里走了n圈，但是慢指针是第一次进环
相遇时有
2 ( a + b ) = a + n ( b + c ) + b a = ( n − 1 ) b + n c a = ( n − 1 ) ( b + c ) + c 2(a+b)=a+n(b+c)+b\\ a=(n-1)b+nc\\ a=(n-1)(b+c)+c 2(a+b)=a+n(b+c)+ba=(n−1)b+nca=(n−1)(b+c)+c
在这一点，我们能得到两段相等的间隔，如果有点从开头走完a，相当于一点走完c并在环里走几圈，如果有两个速度为1的点这样走，它们末了肯定会相遇，而且就是在环的入口处相遇
实现代码：
[*]
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null){
return null;
}
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow){
ListNode tmp = head;
while(tmp != slow){
tmp = tmp.next;
slow = slow.next;
}
return tmp;
}
}
return null;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]