问题背景
想象一个链表，它可能在某个节点处指向一个之前的节点，从而形成一个环。
我们的目标是：
-
判断链表中是否存在环。
-
找到环的入口点。
-
计算环的长度。
比如说这个：
1 -> 2 -> 3 -> 4 -> 5 -> 6^ || v9 <- 8 <- 7
节点 \(4\) 即为环的入口点，环的长度为 \(6\)。
Floyd 判圈算法 (龟兔赛跑算法)
使用两个指针，一个慢指针（乌龟）和一个快指针（兔子）。
慢指针：每次移动一步。
快指针：每次移动两步。
判断是否有环的原理：如果链表中存在环，那么快指针最终会追上慢指针（在环内相遇）。如果不存在环，快指针会先到达链表尾部。
算法步骤如下：
-
初始化：
- 指针 \(slow\) 和 \(fast\) 都指向链表头节点。
-
移动阶段：
- 在每一步中，\(slow\) 向后移动一个节点。
- \(fast\) 向后移动两个节点。
- 检查 \(fast\) 或 \(fast.next\) 是否为 \(null\)。如果是，则链表无环，算法结束。
- 检查 \(slow\) == \(fast\)。如果相等，则链表有环。
-
寻找环入口：
- 当 \(slow\) 和 \(fast\) 第一次相遇时，将其中一个指针重新指向链表头。
- 然后，两个指针都以每次一步的速度移动。
- 当它们再次相遇时，相遇的节点就是环的入口点。
那问题来了，为什么重新指向头节点后，再次相遇的点就是环入口？
我们设链表头到环入口的距离为 \(A\)，环入口到第一次相遇点的距离为 \(B\)，第一次相遇点回到环入口的距离为 \(C\)。
那么环的长度 \(L = B + C\)。
在第一次相遇时：
慢指针走过的路程：\(A + B\)。
快指针走过的路程：\(A + B + k * L\)（其中 \(k\) 是快指针在环内转的圈数）。
由于快指针速度是慢指针的两倍，所以路程也是两倍，所以 \(2(A + B) = A + B + k * L\)，\(A = k * L - B\)。
将 \(L = B + C\) 代入：\(A = k * (B + C) - B\)，\(A = (k-1) * L + C\)。
从链表头（\(A\)）到环入口的距离，等于从第一次相遇点（\(C\)）绕 \((k-1)\) 圈再回到环入口的距离。
所以，一个指针从链表头走 \(A\) 步，另一个指针从相遇点走 \(C + (k-1)*L\) 步，它们最终会在环入口点相遇。
Brent 判圈算法
通常比 Floyd 有更低的时间常数，但好像没啥人学啊。
使用一个慢指针和一个快指针，但快指针不是连续移动，而是“跳跃式”移动。
慢指针：保持不动，直到快指针需要“跳跃”到它的位置。
快指针：每次移动一步，但每走一段距离（\(step_limit\)），如果还没遇到慢指针，就将 \(step_limit\) 翻倍，并把慢指针移动到快指针的当前位置。
算法步骤如下：
- 初始化：
- \(slow\) = \(head\), \(fast\) = \(head\)
- \(step_limit = 2\) （初始的移动限制）
- \(steps_taken = 0\) （记录当前周期内已走的步数）
- 移动阶段：
- \(fast = fast.next\) （快指针走一步）
- \(steps_taken += 1\)
- 检查 \(fast == slow\)。如果相等，则发现环。
- 检查 \(steps_taken == step_limit\)。
- 如果相等，说明当前周期走完了。将 \(slow\) 移动到 \(fast\) 的位置（让乌龟跳到兔子当前位置）。将 \(step_limit *= 2\)，并将 \(steps_taken\) 重置为 \(0\)。
寻找环入口和长度：
一旦检测到环（\(fast\) == \(slow\)），环的长度就是此时 \(steps_taken\) 的值（因为 \(slow\) 没动过，\(fast\) 走了 \(steps_taken\) 步追上它）。
要找到环入口，可以将两个指针都重置为头节点，然后让一个指针先走环长度步，然后两个指针同时一步一步走，相遇点就是入口啦。