下面从算法原理、数学证明、代码实现、变体应用、性能优化、工程实践六个维度，为你全面剖析 Floyd 判环算法（Floyd's Cycle Detection Algorithm），又称龟兔赛跑算法（Tortoise and Hare Algorithm）。一、算法概述核心思想Floyd 算法用两个速度不同的指针遍历链表：慢指针（tortoise）：每次走 1 步快指针（hare）：每次走 2 步如果链表有环，快指针最终会从后面追上慢指针（在环内相遇）；如果无环，快指针会先到达null。为什么叫龟兔赛跑？text想象一个环形跑道： - 乌龟（慢指针）每次走 1 步 - 兔子（快指针）每次走 2 步 - 在环形跑道上，兔子一定会从后面追上乌龟 - 在直线跑道上，兔子会先到达终点二、算法原理与数学证明1. 第一阶段：检测是否有环text设： - 链表头到环入口距离 = a - 环入口到相遇点距离 = b - 环的周长 = c - 慢指针走的步数 = s - 快指针走的步数 = f = 2s（因为速度是 2 倍） 相遇时： - 慢指针在环内走了 b 步，s = a + b - 快指针比慢指针多走了 k 圈（k ≥ 1） f - s = k × c 2s - s = s = k × c 因此：a + b = k × c2. 第二阶段：找环入口（关键证明）text从上面的公式：a + b = k × c 推导：a = k × c - b 这意味着： - 从链表头走 a 步 → 到达环入口 - 从相遇点走 a 步 → 绕环 k 圈后回到环入口 因此：让两个指针分别从头和相遇点同时前进（每次 1 步）， 它们会在环入口相遇！3. 图示说明texta b 头 ────→ ● ──────────→ ● ← 相遇点 ↑ │ │ │ └──────────────┘ (环周长 c) 从头到入口：a 步 从入口到相遇点：b 步 从相遇点回到入口：c - b 步 a = k×c - b → 从头走 a 步 = 从相遇点走 a 步（即 c-b + (k-1)×c）三、代码实现1. 基础版本：检测是否有环javapublic class FloydCycleDetection { /** * 检测链表是否有环 * @return true 有环，false 无环 */ public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head; while (fast != null fast.next != null) { slow = slow.next; // 走 1 步 fast = fast.next.next; // 走 2 步 if (slow == fast) { return true; // 相遇，有环 } } return false; // 快指针到达 null，无环 } }2. 完整版本：找环入口java/** * 检测环并返回环入口节点 * @return 环入口节点（无环返回 null） */ public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode slow = head; ListNode fast = head; // 第一阶段：检测是否有环 while (fast != null fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // 第二阶段：找环入口 ListNode ptr = head; while (ptr != slow) { ptr = ptr.next; slow = slow.next; } return ptr; // 环入口 } } return null; // 无环 }3. 计算环的长度java/** * 计算环的长度 */ public int cycleLength(ListNode head) { if (head == null || head.next == null) { return 0; }
Floyd 判环算法
下面从算法原理、数学证明、代码实现、变体应用、性能优化、工程实践六个维度，为你全面剖析 Floyd 判环算法（Floyd's Cycle Detection Algorithm），又称龟兔赛跑算法（Tortoise and Hare Algorithm）。一、算法概述核心思想Floyd 算法用两个速度不同的指针遍历链表：慢指针（tortoise）：每次走 1 步快指针（hare）：每次走 2 步如果链表有环，快指针最终会从后面追上慢指针（在环内相遇）；如果无环，快指针会先到达null。为什么叫龟兔赛跑？text想象一个环形跑道： - 乌龟（慢指针）每次走 1 步 - 兔子（快指针）每次走 2 步 - 在环形跑道上，兔子一定会从后面追上乌龟 - 在直线跑道上，兔子会先到达终点二、算法原理与数学证明1. 第一阶段：检测是否有环text设： - 链表头到环入口距离 = a - 环入口到相遇点距离 = b - 环的周长 = c - 慢指针走的步数 = s - 快指针走的步数 = f = 2s（因为速度是 2 倍） 相遇时： - 慢指针在环内走了 b 步，s = a + b - 快指针比慢指针多走了 k 圈（k ≥ 1） f - s = k × c 2s - s = s = k × c 因此：a + b = k × c2. 第二阶段：找环入口（关键证明）text从上面的公式：a + b = k × c 推导：a = k × c - b 这意味着： - 从链表头走 a 步 → 到达环入口 - 从相遇点走 a 步 → 绕环 k 圈后回到环入口 因此：让两个指针分别从头和相遇点同时前进（每次 1 步）， 它们会在环入口相遇！3. 图示说明texta b 头 ────→ ● ──────────→ ● ← 相遇点 ↑ │ │ │ └──────────────┘ (环周长 c) 从头到入口：a 步 从入口到相遇点：b 步 从相遇点回到入口：c - b 步 a = k×c - b → 从头走 a 步 = 从相遇点走 a 步（即 c-b + (k-1)×c）三、代码实现1. 基础版本：检测是否有环javapublic class FloydCycleDetection { /** * 检测链表是否有环 * @return true 有环，false 无环 */ public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head; while (fast != null fast.next != null) { slow = slow.next; // 走 1 步 fast = fast.next.next; // 走 2 步 if (slow == fast) { return true; // 相遇，有环 } } return false; // 快指针到达 null，无环 } }2. 完整版本：找环入口java/** * 检测环并返回环入口节点 * @return 环入口节点（无环返回 null） */ public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode slow = head; ListNode fast = head; // 第一阶段：检测是否有环 while (fast != null fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // 第二阶段：找环入口 ListNode ptr = head; while (ptr != slow) { ptr = ptr.next; slow = slow.next; } return ptr; // 环入口 } } return null; // 无环 }3. 计算环的长度java/** * 计算环的长度 */ public int cycleLength(ListNode head) { if (head == null || head.next == null) { return 0; }
