—— 基于快慢指针（Floyd 判圈算法）
一、问题背景
在单链表中，某些节点的 next 指针可能会指向链表中已经出现过的节点，从而形成 环形结构。
常见问题包括：
- 判断链表是否存在环
- 如果存在环，找到 环的入口节点
二、链表节点定义
class ListNode
{public int value;public ListNode next;
}
value：节点存储的数据next：指向下一个节点的引用
三、核心思想：快慢指针（Floyd 判圈算法）
指针定义
- 慢指针（slowPointer）
- 每次向前移动 1 步
- 快指针（fastPointer）
- 每次向前移动 2 步
slow: 1 step / loop
fast: 2 steps / loop
四、判环原理说明
1. 无环情况
- 快指针会率先走到链表末尾
- 出现
fast == null或fast.next == null - 直接判定：无环
2. 有环情况
- 快指针与慢指针都会进入环中
- 快指针速度更快
- 在环中必然会 追上慢指针
- 一旦出现：
slowPointer == fastPointer
即可确认链表存在环
五、判环代码实现
static bool HasCycle(ListNode node)
{if (node == null || node.next == null){return false;}ListNode slowPointer = node;ListNode fastPointer = node;while (fastPointer != null && fastPointer.next != null){slowPointer = slowPointer.next;fastPointer = fastPointer.next.next;if (slowPointer == fastPointer){// 发现环return true;}}return false;
}
六、为什么快慢指针一定能相遇？
设：
- 从链表头到环入口的长度为
a - 环的长度为
b
当慢指针进入环时： - 快指针已经在环中领先若干步
- 两者在环中相对速度为
1 - 相对位移在
b的模意义下递增
因此：
必然在有限步内相遇
七、寻找环入口的数学原理
当快慢指针第一次相遇时：
- 将 快指针重新指向链表头
- 慢指针保持在相遇点
- 两个指针 每次都走 1 步
- 再次相遇的节点，就是 环入口
八、查找环入口的代码实现
if (slowPointer == fastPointer)
{fastPointer = node; // 重置快指针到链表头while (slowPointer != fastPointer){slowPointer = slowPointer.next;fastPointer = fastPointer.next;}Console.WriteLine($"环入口是值为 {slowPointer.value} 的节点");return true;
}
九、完整算法流程总结
1. 初始化 slow 和 fast 指针指向头节点
2. slow 每次走 1 步，fast 每次走 2 步
3. 若 fast 走到 null，说明无环
4. 若 slow == fast，说明有环
5. fast 重置到头节点
6. slow 与 fast 同速前进
7. 再次相遇点即为环入口
十、时间与空间复杂度分析
时间复杂度
- 判环：O(n)
- 找入口：O(n)
总时间复杂度：O(n)
空间复杂度
- 只使用常数个指针
空间复杂度：O(1)