1. 概述
在本篇文章中，我们将学习如何在存在环的单链表中找到环的起点节点。我们会分析不同方法的时间和空间复杂度，重点介绍最高效的算法 Floyd 判圈算法（又称“龟兔赛跑算法”），并详细解释其原理与数学证明。
该算法的时间复杂度为 **O(n)**，空间复杂度为 **O(1)**，是解决此类问题的经典方案。
2. 问题描述
我们有一个单链表，并且这个链表中包含一个环。我们的任务是找出环的起始节点（cycle start node）。输入只有一个参数：链表的头节点（head）。
举个例子：
在这个例子中，链表从节点 1 开始，经过节点 2、3、4，进入环 4 → 5 → 6 → 7 → 8 → 9 → 4。因此，环的起点节点是 4。我们的目标就是返回这个节点。
3. 龟兔赛跑算法（Hare and Tortoise）
3.1 算法思想
Floyd 的龟兔赛跑算法使用两个指针：一个“慢指针”（tortoise）每次移动一个节点，一个“快指针”（hare）每次移动两个节点。
- 如果链表中没有环，快指针最终会到达 null。
- 如果有环，两个指针最终会在环内相遇。
关键步骤如下：
✅ 第一阶段：快慢指针同时从 head 出发，直到它们在环内相遇。
✅ 第二阶段：将快指针重置为 head，然后两个指针以相同速度（一次一步）继续移动，再次相遇的节点就是环的起点。
3.2 算法演示
初始状态：
快慢指针从节点 1 出发，快指针速度是慢指针的两倍。
经过若干步后，两者在节点 7 相遇：
此时将快指针重置为 head（节点 1），并将两个指针速度调为一致（一次一步）：
再次相遇的节点 4 即为环的起点。
4. 算法证明
4.1 第一次相遇
设：
M为从链表头到环起点的距离。L为环的长度。Y为从环起点到相遇点的距离。Z = L - Y为从相遇点绕环回到起点的距离。
快指针走过的总距离为：
H = M + a * L + Y
慢指针走过的总距离为：
T = M + Y
因为快指针速度是慢指针的两倍，所以有：
H = 2 * T
代入得：
M + a * L + Y = 2 * (M + Y)
化简后：
M + Y = a * L
又因为 Y = L - Z，代入得：
M + L - Z = a * L
=> M = (a - 1) * L + Z
对两边取模 L 得：
M mod L = Z
这说明从 head 出发走 M 步后，正好到达环起点；而从相遇点出发走 Z 步，也到达环起点。
4.2 算法正确性
在第二阶段，快指针从 head 出发，慢指针从相遇点出发，两者速度一致：
- 快指针走 M 步到达环起点。
- 慢指针走 Z 步也到达环起点。
因为 M mod L = Z，所以两者会同时到达环起点，算法正确。
5. 时间与空间复杂度分析
时间复杂度：O(n)
- 第一阶段：快慢指针最多走
n + L步（n 为链表总长度，L 为环长）。 - 第二阶段：最多走
M步，M ≤ n。 - 总体复杂度仍为 O(n)。
空间复杂度：O(1)
仅使用两个指针变量，空间固定。
6. 总结
本文介绍了在单链表中查找环起点的两种思路：
- ✅ 哈希集合法：简单直观，但空间复杂度 O(n)。
- ✅ Floyd 判圈算法：空间复杂度 O(1)，时间复杂度 O(n)，是更优解。
该算法不仅适用于链表环检测，还可用于解决类似问题，例如：
- LeetCode 287 题：查找数组中重复的数字。
- 判断链表中是否有环。
- 查找链表的中间节点。
掌握 Floyd 判圈算法是每个程序员必备的基本技能之一，尤其在面试中频繁出现，建议多加练习。