一、算法介绍
Floyd 龟兔赛跑算法（也称为 Floyd 判圈算法或 Floyd 循环检测算法）
是一种用于检测链表中是否存在环的算法。如果链表上存在环，那么在环上以不同速度前进的两个指针必定会在某个时刻相遇。
1.判断是否有环
龟一次走一步，兔子一次走两步：
- 当兔子能走到终点时，不存在环
- 当兔子能追上龟时，存在环
2.寻找环入口
从它们第一次相遇开始，龟回到起点，兔子保持原位不变
- 龟和兔子一次都走一步
- 当再次相遇时，地点就是环的入口
设起点到环入口长度为步，环的长度为
步，那么
步的长度为环的入口处。(因为环的长度是y，一个y就是从起点到终点，n个y就是重叠了n次，还是在入口处)
第一次相遇龟和兔走的路程：
-
（必须是在绕环的过程中才能追上龟）
-
（
）
因为兔子的距离是乌龟的两倍（兔子一次2步，乌龟一次1步），所以：
所以乌龟走的距离正好是整数倍的环长度，即。
根据前面环入口处的长度为，所以，在乌龟和兔子相遇之后，乌龟只需要再走
步，此时距离就为
，即环入口的长度。
此时，要计算出为具体为多少，可以让兔子模拟乌龟（即每次只走一步），那么兔子需要前进
步走到环入口；让乌龟回到起点，乌龟前进
步也能走到环入口，所以
的值就是他们相遇时候所走的步数；即相遇的点就是环的入口。
二、Leetcode141.环形链表（判断是否有环）
判断是否有环：
使用两个指针，一个快指针和一个慢指针，分别以不同的速度遍历链表，两个指针相遇代表有环，否则无环。
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode fast = head;
ListNode slow = head;
while (true) {
fast = fast.next.next;
slow = slow.next;
// 有环
if (fast == slow) {
return true;
}
// 无环
if (fast == null || fast.next == null) {
return false;
}
}
}
三、Leetcode142.环形链表II（寻找环入口）
寻找环的入口：
在第一次相遇后，将 slow 指针重新指向链表头节点，然后 slow 和 fast 指针都以相同的速度（每次移动一步）前进，当它们再次相遇时，相遇点即为环的入口点。
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (true) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
// 相遇 让slow回到起点
slow = head;
while (fast != slow) {
// 分别前进一步
fast = fast.next;
slow = slow.next;
}
return slow;
}
if (fast == null || fast.next == null) {
return null;
}
}
}
