每日算法 — 使用java实现Floyd判圈：双指针快慢检测环与环起点定位

引言

Floyd判圈算法（Floyd’s Cycle-Finding Algorithm），又称龟兔赛跑算法（Tortoise and Hare），是计算机科学中检测链表中是否存在环的经典算法。该算法由Robert W. Floyd于1967年提出，仅使用两个移动速度不同的指针，即可在O(n)时间复杂度和O(1)空间复杂度内完成环的检测，并能进一步定位环的入口位置。本文将用Java完整实现该算法，并深入分析其数学原理与复杂度。

算法原理

核心思想

设链表中有环，快指针（hare）每次移动两步，慢指针（tortoise）每次移动一步。如果存在环，快指针终将追上慢指针；若无环，快指针会先到达链表末尾。

为什么快指针两步、慢指针一步？

考虑相对速度：快指针相对慢指针的速度为1步/单位时间。若环长度为C，则两者之间的相对距离每次减少1。因此最多经过C步，快指针必然与慢指针相遇。

环入口定位的数学推导

设链表头到环入口距离为a，环入口到相遇点距离为b，相遇点回到环入口距离为c。则：
– 慢指针走过的距离：a + b
– 快指针走过的距离：a + b + k(b + c) = 2(a + b)（k为快指针绕环圈数）

整理得：a = k(b + c) – b = (k-1)(b + c) + c

这意味着：从链表头出发一个指针，从相遇点出发另一个指针，两者同步移动，最终会在环入口相遇。

Java实现

import java.util.Objects;

/**
 * Floyd判圈算法实现
 * 包含环检测、环入口定位、环长度计算三个核心功能
 */
public class FloydCycleDetection {

    /**
     * 链表节点定义
     */
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 检测链表中是否存在环
     * 时间复杂度: O(n)，空间复杂度: O(1)
     *
     * @param head 链表头节点
     * @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;          // 龟走一步
            fast = fast.next.next;     // 兔走两步

            if (slow == fast) {
                return true;  // 相遇，存在环
            }
        }

        return false;  // 快指针到达末尾，无环
    }

    /**
     * 定位环的入口节点
     * 分两步：1) 找到相遇点 2) 一个指针回到头部，同步移动找入口
     *
     * @param head 链表头节点
     * @return 环入口节点，无环返回null
     */
    public ListNode detectCycleEntry(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        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;
        }

        // 第二阶段：定位环入口
        // 数学证明：从head和相遇点同时出发的指针会在入口相遇
        ListNode ptr1 = head;
        ListNode ptr2 = slow;  // 相遇点

        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }

        return ptr1;  // 环入口
    }

    /**
     * 计算环的长度
     *
     * @param head 链表头节点
     * @return 环的长度，无环返回0
     */
    public int cycleLength(ListNode head) {
        ListNode entry = detectCycleEntry(head);
        if (entry == null) {
            return 0;
        }

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

    // ==================== 测试与演示 ====================

    public static void main(String[] args) {
        FloydCycleDetection solver = new FloydCycleDetection();

        // 构建测试链表：1 -> 2 -> 3 -> 4 -> 5 -> 3(环回到节点3)
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node3;  // 形成环，入口为节点3

        System.out.println("=== Floyd判圈算法测试 ===");
        System.out.println("链表: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (环)");
        System.out.println("是否有环: " + solver.hasCycle(node1));

        ListNode entry = solver.detectCycleEntry(node1);
        System.out.println("环入口值: " + (entry != null ? entry.val : "null"));

        int len = solver.cycleLength(node1);
        System.out.println("环长度: " + len);

        // 测试无环链表
        ListNode nodeA = new ListNode(10);
        nodeA.next = new ListNode(20);
        nodeA.next.next = new ListNode(30);

        System.out.println("\n无环链表: 10 -> 20 -> 30");
        System.out.println("是否有环: " + solver.hasCycle(nodeA));
        System.out.println("环入口: " + solver.detectCycleEntry(nodeA));
    }
}

复杂度分析

应用场景

1. 链表环检测：LeetCode 141、142的经典解法
2. 重复元素检测：利用类似思想检测数组中的重复数（LeetCode 287）
3. 序列周期检测：在伪随机数生成器中检测周期
4. 分布式系统：检测网络拓扑中的环路

总结

Floyd判圈算法是双指针技巧的典型代表，其核心在于利用相对速度差确保相遇，以及精妙的数学推导定位环入口。掌握该算法不仅能解决链表环问题，更能培养对指针运动和相对速度的直觉理解。