参考上面的blog，加上自己的证明思路
方法在网上很多了，简单说明如下：
两个指针同时从链表头出发，A指针的步长为1，B指针的步长为2，如果两个指针能重叠，则说明链表有环。
当指针重叠之后，将B指针移回链表头，以步长为1移动，直到两个指针再次重合的时候，即为环的入口。
证明如下：
假设链表头到环入口的近距离为L，在时刻t两个指针重合，环的长度是C，A指针绕环走了至少m圈，b指针绕环走了至少n圈，则有如下等式：
t-L-m*c = 2t-L-n*c => t=(n-m)*c
此时A指针相对环入口所在的偏移位置p为：
p = (t-L) mod C => p = ((n-m)*c-L) mod C => p = C-(L mod C)
这是讲B指针移到链表头，以步长为1移动，假设经过t1时刻后两个指针在环入口相遇，则有如下等式：
(p+t1) mod C = 0 => (C - (L mod C) + t1) mod C = 0 => t1 mod C - L mod C = 0 => t1 = L
即在L步之后，两个指针在环入口相遇
阅读(1894) | 评论(0) | 转发(0) |
