一道leetcode快慢指针的题目

hui00000

假设链表在环开始前有n1个结点，成环的结点个数为n2，这里的n1、n2以及后面的x、m都是正整数
先分析第一次相遇
第一次相遇的时候，假设慢指针走了一共走了x步，考虑到相遇了，那么必有x>n1，即慢指针在无环的区域走了n1个结点，在环里面走了x-n1个结点；考虑到，快指针的速度是慢指针的两倍，这个时候，快指针走了一共走了2x-1步，快指针在无环的区域走了n1个结点，在环里面走了2x-n1-1个结点；
考虑到相遇的情况，则快指针比慢指针在环里面多走的结点数一定是环结点数的倍数，即 (2x-n1-1)-(x-n1)=n2的倍数，化简后是x-1=n2的倍数，可以表示为x=m*n2+1。
接下来看第二次相遇
从第一次相遇到第二次相遇，走的结点数量可以由快指针确定，即n1，第二次相遇的时候，慢指针一共走了x+n1步，其中慢指针在无环的区域走了n1个结点，在环里面走了x个结点，换个说法，慢指针在环里面走了m*n2+1个结点，即走了m圈之后，又走了一步，即所处位置为进入环的第一个位置，也就是环的起点。

QingYi.

在LeetCode 的 Commit and Solution中 有很多优质的解释

lidelongqi

• 使用双指针判断链表中是否有环，慢指针slow每次走一步，快指针fast每次走两步，若链表中有环，则两指针必定相遇。
• 假设环的长度为L，环上入口距离链表头距离为a，两指针第一次相遇处距离环入口为b，则另一段环的长度为c=L-b，由于快指针走过的距离是慢指针的两倍，则有a+L+b=2*(a+b),又有L=b+c，可得a=c，故当判断有环时(slow==fast)时，移动头指针，同时移动慢指针，两指针相遇处即为环的入口。
  

c03xp

妙啊。。。