当前位置：首页 > news >正文

图解Floyd判圈算法 | 从龟兔赛跑到Java实战，一文学会环检测与定位

news 2026/8/2 12:54:30

1. Floyd判圈算法概述

想象一下龟兔赛跑的场景：兔子跑得快，乌龟跑得慢。如果在直线跑道上比赛，兔子会一直领先；但如果跑道是个环形，兔子最终会追上乌龟。这就是Floyd判圈算法最形象的比喻——因此它也被称为龟兔赛跑算法。

这个算法由计算机科学家Robert W. Floyd在1967年提出，最初用于检测有限状态机中的循环。如今它已成为解决链表环检测问题的经典方案。算法的核心在于使用双指针（快指针和慢指针），通过不同的移动速度来探测环的存在。

为什么需要这个算法？在实际开发中，我们经常遇到需要检测循环的场景。比如：

检查链表是否存在环状引用
分析迭代函数的收敛性
检测内存泄漏时的循环引用
解决LeetCode上的环形链表问题

算法的精妙之处在于，它不仅能够判断环是否存在，还能准确定位环的起点并计算环的长度——所有这些操作的时间复杂度都是O(n)，空间复杂度仅为O(1)。

2. 如何判断链表是否有环

2.1 双指针的移动策略

让我们用Java代码来具体实现这个判断过程。假设我们有一个链表节点类：

class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } }

判断环存在的核心逻辑如下：

初始化两个指针都指向头节点
慢指针每次移动一步，快指针每次移动两步
如果快指针遇到null，说明链表无环
如果两个指针相遇，则链表有环

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; fast = fast.next.next; if (slow == fast) { return true; } } return false; }

2.2 为什么这样能检测到环？

回到龟兔赛跑的比喻：

在无环情况下，兔子（快指针）会先到达终点（null）
有环时，兔子会在环内绕圈，最终与乌龟（慢指针）相遇

数学上可以证明，如果存在环，快慢指针必定会在有限时间内相遇。假设环外有L个节点，环内有C个节点：

慢指针进入环时，快指针已经在环内某处
快指针相对于慢指针的速度是1步/单位时间
最坏情况下，快指针需要追赶C-1步
因此时间复杂度为O(L+C)，即O(n)

3. 定位环的起点

3.1 相遇后的处理策略

仅仅知道环存在还不够，我们经常需要找到环的起始节点。Floyd算法的精妙之处在于，它还能准确定位环的起点。方法如下：

当快慢指针首次相遇时，保持快指针位置不变
将慢指针移回链表头部
两个指针现在都以相同速度（每次一步）前进
它们再次相遇的节点就是环的起点

public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; // 第一阶段：检测是否有环 while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // 第二阶段：寻找环起点 slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } } return null; }

3.2 数学原理揭秘

这个看似神奇的方法其实有严谨的数学基础。设：

链表头到环起点的距离为L
环起点到首次相遇点的距离为K
环长度为C

当首次相遇时：

慢指针走了L+K步
快指针走了L+K+nC步（n是快指针绕环的圈数）
因为快指针速度是慢指针的两倍：2(L+K) = L+K+nC
化简得：L = nC - K

这意味着：从链表头走L步，等于从相遇点走nC-K步。因此，两个指针以相同速度前进时，必然在环起点相遇。

4. 计算环的长度

4.1 三种实用方法

知道环的起点后，计算环长度就简单了。这里介绍三种常用方法：

方法一：从环起点遍历

int lengthFromEntry(ListNode entry) { int length = 1; ListNode current = entry.next; while (current != entry) { length++; current = current.next; } return length; }

方法二：利用相遇点计数

int lengthFromMeeting(ListNode meeting) { int length = 1; ListNode current = meeting.next; while (current != meeting) { length++; current = current.next; } return length; }

方法三：优化后的双指针法

int getCycleLength(ListNode head) { ListNode slow = head; ListNode fast = head; // 找到相遇点 while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // 计算环长度 int length = 0; do { slow = slow.next; length++; } while (slow != fast); return length; } } return 0; }

4.2 性能比较

这三种方法各有优劣：

方法一需要先找到环起点，时间复杂度O(n)+O(C)
方法二直接利用相遇点，时间复杂度O(C)
方法三在检测环的同时计算长度，最节省时间

实际应用中，如果只需要环长度而不需要起点，方法二是最优选择。

5. 完整Java实战代码

下面是一个完整的可运行示例，包含链表构建、环检测、起点定位和长度计算：

public class FloydCycleDetection { static class ListNode { int val; ListNode next; ListNode(int x) { val = x; next = null; } } // 构建带环链表 public static ListNode createCycleList(int nonCycleLen, int cycleLen) { if (cycleLen <= 0) { throw new IllegalArgumentException("Cycle length must be positive"); } ListNode dummy = new ListNode(0); ListNode current = dummy; ListNode cycleEntry = null; // 构建非环部分 for (int i = 1; i <= nonCycleLen; i++) { current.next = new ListNode(i); current = current.next; if (i == nonCycleLen) { cycleEntry = current; // 标记环入口 } } // 构建环部分 ListNode cycleEnd = cycleEntry; for (int i = 1; i < cycleLen; i++) { cycleEnd.next = new ListNode(nonCycleLen + i); cycleEnd = cycleEnd.next; } cycleEnd.next = cycleEntry; // 形成环 return dummy.next; } // 检测环是否存在 public static boolean hasCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; } // 定位环起点 public static ListNode findCycleEntry(ListNode head) { ListNode slow = head; ListNode fast = head; boolean hasCycle = false; // 检测环并找到相遇点 while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { hasCycle = true; break; } } if (!hasCycle) return null; // 寻找环入口 slow = head; while (slow != fast) { slow = slow.next; fast = fast.next; } return slow; } // 计算环长度 public static int getCycleLength(ListNode entry) { int length = 1; ListNode current = entry.next; while (current != entry) { length++; current = current.next; } return length; } public static void main(String[] args) { // 构建链表：非环部分3个节点，环部分4个节点 ListNode list = createCycleList(3, 4); System.out.println("Has cycle: " + hasCycle(list)); ListNode entry = findCycleEntry(list); System.out.println("Cycle entry: " + (entry != null ? entry.val : "null")); if (entry != null) { System.out.println("Cycle length: " + getCycleLength(entry)); } } }