​ Floyd判圈算法(Floyd Cycle Detection Algorithm)，又称龟兔赛跑算法(Tortoise and Hare Algorithm)，是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，求出该环的起点与长度的算法。该算法据高德纳称由美国科学家罗伯特·弗洛伊德发明，但这一算法并没有出现在罗伯特·弗洛伊德公开发表的著作中。

问题：

​ 如何检测一个链表是否有环，如果有，那么如何确定环的起点.

要求：

​ 空间复杂度为O(1), 时间复杂度为O(n).

对于一个有环的链表，利用Floyd算法可以做到下面三件事：

  1. 判断是否有环
  2. 计算环的长度
  3. 寻找环的起点

image-20200611083243900

1.判断是否有环

​ 使用两个指针slow和fast。两个指针都从链表的起始处S开始。slow每次向后移动一步，fast每次向后移动两步。若在fast到达链表尾部前slow与fast相遇了，就说明链表有环。
这里可以简单的证明一下：反证法，假如没有环，那么slow永远追不上fast，那么在fast到达链表尾部前slow不会fast相遇了。若相遇了，链表就有环。

2.求环的长度

​ 当slow和fast相遇时，slow和fast必定在环上，所以只要让一者不动，另一者走一圈直到相遇，走过的节点数就是环的长度。

3.求环的起点

如图所示，设AB=n, SA=m。设环的长度为L。
假设slow走过的节点数为i，那么有：
i = m + n + aL a为slow绕过的环的圈数。
因为fast速度为slow的两倍，所以相同时间走过的节点数为slow的两倍，所以有：
2i = m + n + b*L b为fast绕过的环的圈数。
两者做差有 : i = (b-a)*L。
所以可知，fast和slow走过的距离是环的整数倍。
所以有m+n=(b-2a)L。
所以此时让slow回到起点S，，fast仍然在B。
让两个指针以每次一步的速度往前走。
当走了m步时，可发现slow和fast正好都在A处，即是环的起点。