算法：龟兔赛跑

1. 龟兔赛跑？

龟兔赛跑算法（Floyd's cycle detection 或 Tortoise and the hare algorithm）可用于判定链表、迭代函数、有限状态机是否有环。如果有环，可以找出环的起点和大小。

2. 基本原理？

龟兔赛跑的基本思想可以用我们跑步的例子来解释，如果两个人同时出发，如果赛道有环，那么快的一方总能追上慢的一方。

定义：有限集 S，Xi∈S，f(Xi)∈S，Xi=f(Xi-1)；

假设：μ 是环路的起点，λ是环路长度；

如果存在环路，则存在 i ≥ μ，k ≥ 0，使：

Xi = X(i + kλ)；

该算法主要回答3个问题

1. 是否有环路？

2. 环路的起点？

3. 环路的长度？

假设有一只兔子（Hare）和一只乌龟（Tortoise），它们从链表的开始以不同的速度沿着链表遍历。乌龟每一步移动1个单元格，兔子每一步移动2个单元格。

2.1. 是否有环路？

如果兔子没路走了，意味着有终点，即没有循环。

2.1. 环路的起点？

如果包含一个环，兔子会先进入环，随后和后来的乌龟相遇。

【性质1】：存在 i=kλ≥μ 使 Xi = X2i；所以当龟、兔第一次相遇时，乌龟走过的步长即是 kλ。

【性质2】：当已求得某个 v=kλ 时，根据 Xi = X(i+v) (i≥μ)，只要在让乌龟回到起点，乌龟和兔子每次走一个单元格，再一次相遇时，i 就是 μ，即它们相遇的位置就是环路起点。

2.3. 环路的长度？

【性质3】：兔子、乌龟第二次在起点相遇后，它们都停在环路的起点上。此时兔子不动，乌龟继续走，每一步走1个单元格，当第三次相遇时，乌龟走过的路程即环路长度。

3. 动画展示？

图：龟兔赛跑动画演示

图文无关

4. 代码示例？

5. 算法特性？

• 时间复杂度：O(λ+μ)

参考：

《算法基础》 维基百科： https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare 动画展示： https://visualgo.net/en/cyclefinding?slide=1