floyd判圈算法又称龟兔赛跑算法
算法流程
两个指针(P1,P2)
(P1)每次向后跳一次
(P2)每次向后跳两次
显然,如果(P1,P2)相遇才有环
现在我们想求环长和环的起点.
设起点到环的距离为(len)
环的起点离相遇点距离(rem)
设两个指针分别走了(p,q)步
那么,(p=len+rem+A*L, q=len+rem+B*L)
又有(2p=q)
可以得到(p=(A-B)L)
说明了(p,q)是(L)的倍数
我们再把(p)挪回起点,(p,q)同时每次走一步,直到相遇
那么(q=2p+len)
等于(q)从起点走了(len)步然后走了(2(A-B))圈
所以(p,q)会在环的起点处相遇.
然后继续跳即可求出环长.