有环单链表的环长、环起点和链表长

**Floyd判圈算法(Floyd Cycle Detection Algorithm)**，又称 **龟兔赛跑算法(Tortoise and Hare Algorithm)**，是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，求出该环的起点与长度的算法。

---

1、判断单链表是否有环

使用两个 slow, fast 指针从头开始扫描链表。指针slow 每次走1步，指针fast每次走2步。如果存在环，则指针slow、fast会相遇；如果不存在环，指针fast遇到NULL退出。

就是所谓的追击相遇问题：

---

2、求有环单链表的环长

在环上相遇后，记录第一次相遇点为Pos，之后指针slow继续每次走1步，fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈，也就是多走的距离等于环长。

设从第一次相遇到第二次相遇，设slow走了len步，则fast走了2×len步，相遇时多走了一圈：
环长=2×len-len。

---

3、求有环单链表的环连接点位置

在环上相遇后，记录第一次相遇点为Pos，连接点为Join，假设头结点到连接点的长度为LenA，连接点到第一次相遇点的长度为x，环长为R。
第一次相遇时，slow走的长度 S = LenA + x;
第一次相遇时，fast走的长度 2S = LenA + n×R + x;
所以可以知道，LenA + x = n×R;
所以LenA = n×R -x;
这个式子的意思是，第一次相遇后，如果一个指针p1从头开始走，另一个指针p2从相遇点开始走，则p1走到距离LenA处（即相遇点）时，p2走的距离为n×R -x，而n×R -x就是从相遇点绕环n圈后到环入口的距离，所以p2此时肯定也位于环入口处。
结论就是：
快慢指针第一次相遇后，一个指针从头开始以步长1前进，另一个指针继续从相遇点开始以步长1前进，则下一次相遇点就是环入口。

---

4、求有环单链表的链表长

上述2中求出了环的长度，3中求出了连接点的位置，也就是求出了头结点到连接点的长度，两者相加就是链表的长度。

参考：求有环单链表中的环长、环起点、链表长
https://www.cnblogs.com/xudong-bupt/p/3667729.html

---