Floyd判圈算法（龟兔赛跑算法, Floyd's cycle detection）及其证明

问题：如何检测一个链表是否有环（循环节），如果有，那么如何确定环的起点以及环的长度。
空间要求：不能存储所经过的的每一个点。
举例： x0=1 x 0 = 1 $x_0 = 1$, xi+1=f(xi) x i + 1 = f ( x i ) $x_{i+1} = f(x_i)$，求循环节的起始位置以及循环节的长度。

1.判断是否有环

使用两个指针slow和fast。两个指针开始时均在头节点处( S S $S$点)，slow指针（龟）一次向后移动一个一步，fast指针（兔）一次向后移动两步。若存在环，则slow和fast必能相遇；反之若slow到达链表尾时两个指针仍不能相遇，则不存在环。
证明
设头节点S$S$$S$与循环节起始点 A A $A$之间举例|SA|=m$|SA|=m$$|SA|=m$。两个指针在 B B $B$点相遇，|AB|=n$|AB|=n$$|AB|=n$。可知环中的点满足 xi=xi+kl x i = x i + k l $x_i = x_{i+kl}$，其中 l l $l$为循环节的长度，也就是说fast比slow多走了整数圈。当i=kl$i=kl$$i = kl$时，满足 xi=x2i x i = x 2 i $x_i = x_{2i}$，这样的 i i $i$一定存在，得证。

2.计算环的长度

这一步比较简单，让其中一个指针停在B$B$$B$不动，另一个一步一步向前走并记录步数，再次相遇时步数即为环的长度。

3.寻找环的起点

其中一个指针在 B B $B$不动，另一个放到起点S$S$$S$，两个指针同时一步一步移动，则两指针将会在循环节的起点相遇。
证明
B B $B$点的下标 i=kl$i=kl$$i = kl$为 l l $l$的整数倍。当放到S$S$$S$处的指针移动 m m $m$到达A$A$$A$时，放在 B B $B$的指针移动到i+m=kl+m$i+m=kl+m$$i+m=kl+m$处，于是两个指针相遇。

代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e7;
int f(int x)
{
    int res = 0;
    //此处填写递推式，使其走到下一步
    return res;
}
//ori为起点处的值，len为循环节长度，id为循环节起始处坐标，val为循环节起始处的值
bool FloydCycle(int ori, int &len, int &id,  int &val)//有环返回true，无环返回false
{
    int slow, fast;//慢指针和快指针
    slow = f(ori);//快指针的移动速度是慢指针的2倍
    fast = f(f(ori));
    int cnt = 1;
    while(slow != fast && cnt <= maxn)//maxn为链表尾节点
    {
        //快指针的移动速度是慢指针的2倍
        slow = f(slow);
        fast = f(f(fast));
        cnt++;
    }
    if(slow != fast) return false;//无环

    len = 1;//环的长度
    slow = f(slow);
    while(slow != fast)
    {
        slow = f(slow);
        len++;
    }

    id = 0;
    slow = 1;
    while(slow != fast)
    {
        slow = f(slow);
        fast = f(fast);
        id++;
    }
    val = slow;

    return true;
}