Floyd判圈算法（Floyd's Cycle-Finding Algorithm） 描述 Floyd判圈算法用于检测一个链表或序列中是否存在环（循环）。该算法通过两个指针以不同速度遍历链表，若存在环，则快指针最终会追上慢指针。算法时间复杂度为O(n)，空间复杂度为O(1)，仅需两个指针的额外空间。 解题过程 问题分析 给定一个链表，判断其是否包含环。 若使用哈希表存储访问过的节点，需O(n)空间。Floyd算法通过指针技巧避免额外空间。 算法核心思想 使用两个指针：慢指针（每次移动1步）和快指针（每次移动2步）。 若链表无环，快指针会先到达终点（null）。 若链表有环，快指针会先进入环，慢指针后进入。由于快指针速度是慢指针的2倍，在环内快指针会从后方追上慢指针（相遇）。 步骤详解 步骤1：初始化指针 慢指针 slow 和快指针 fast 均指向链表头节点。 步骤2：移动指针 慢指针每次移动1步： slow = slow.next 。 快指针每次移动2步： fast = fast.next.next （需先检查 fast 和 fast.next 是否为空）。 重复移动，直到： fast 为 null 或 fast.next 为 null ：说明无环，返回 false 。 slow == fast ：说明有环，返回 true 。 步骤3：原理证明（为什么快指针不会跳过慢指针？） 设慢指针进入环时，快指针已在环中，且两指针距离为k（0 ≤ k < 环长）。 每移动一次，快指针追近1步（快指针速度差为1），距离变为k-1, k-2, ..., 0。 因此快指针最多追k次就会相遇，不会跳过慢指针。 扩展应用：确定环的起点 当快慢指针相遇后，将慢指针重新指向链表头，快指针留在相遇点。 两指针改为同速（每次1步）移动，再次相遇的节点即为环的起点。 原理 ：设头到环起点距离为a，环起点到相遇点距离为b，环长为L。第一次相遇时，慢指针走了a+b，快指针走了2(a+b) = a + b + nL（n为快指针绕环圈数）。解得a = nL - b，即从头到环起点的距离等于相遇点绕环n圈再走回环起点的距离。 示例验证 链表：1→2→3→4→5→3（环从3开始）。 步骤： 慢指针：1→2→3→4；快指针：1→3→5→3→5→... 相遇于节点4（实际路径可自行模拟）。 找环起点：慢指针回头部，快指针在4；同速移动，慢指针从1到3，快指针从4到5到3，相遇于3（环起点）。 总结 Floyd算法通过双指针的巧妙速度差，以O(1)空间高效解决环检测问题，并可通过二次同速移动定位环起点，是链表环问题的经典解法。