Java题解环形链表II：Floyd判圈算法与双指针推导

如果你刷过力扣热题100里的链表题，大概率会在“环形链表 II”这一题上多停留一会儿。很多人第一次做它的时候，第一反应是“这不就是判断链表有没有环嘛”，然后顺手写出一个布尔值的判断，提交之后才发现题目的真实要求是返回入环点，而不是回答 true 或 false。就因为这一个小小的要求变化，解法直接从“顺着 next 往下走”上升到了双指针加数学推导的层面。

这篇我用 Java 把这道题完整拆一遍，从最直观的哈希表法开始，讲到 Floyd 判圈算法，把“相遇点为什么不是入口”“入口为什么可以靠两段同速移动找出来”这些关键点都讲透。不管你是在准备面试，还是正在按热题清单刷题，看完这一篇，都能做到既会写代码，也能在面试官追问原理的时候从容应对。

1. 题面与直觉：环形链表 II 到底在考什么

1.1 题目描述与样例解读

题目给一个链表头节点 head，链表里可能有环，也可能没有环。如果有环，要返回入环的第一个节点；如果没有环，返回 null。注意这里的“入环点”指的是进入环的那个起始节点，不是快慢指针第一次相遇的位置。

力扣的原题会附带一个 pos 参数，用来表示尾节点指向链表中某个节点的索引，但由于最终的方法签名只接收 head，pos 完全是为了构造测试数据用的。真正写代码的时候，你拿到的只有 head 一个参数。

以经典示例 [3,2,0,-4], pos = 1 来说，链表结构是 3 -> 2 -> 0 -> -4 -> 2，尾节点 -4 的 next 指向了索引 1 的节点 2。在这个例子里，环的入口是 2。

这个例子的好处在于，它直观地暴露了一个常见误区：很多人以为快慢指针停下来的时候，那个位置就是入口，其实不是。在 [3,2,0,-4] 这个链表里，快慢指针第一次碰头发生在 -4 这个节点上，而不是入口节点 2。如果抱着“相遇点就是入口”的想法去写代码，一定会出问题。

1.2 一个最常见的误区

为什么相遇点不等于入口？这得从快慢指针的运动过程说起。慢指针一次走一步，快指针一次走两步，快指针跑得快，会先进入环，然后在环里一圈一圈地绕。慢指针进环以后，快指针可能在它前方任意位置。之后每走一轮，快指针就比慢指针多追近一步，直到某个瞬间两者落在同一个节点上。

这个节点取决于链表的长度、环的长度、入口位置这些具体数值。它可以是环里的任意一个点，但不保证是入口点。所以阶段一撞上的点只能证明“确实有环”，不能直接拿来当答案返回。很多初学者在这里栽跟头，就是没有意识到“找相遇点”和“找入口点”是两件事。

正确思路应该分两步：先判断有没有环，再通过环的长度或者数学关系把入口点定位出来。而这个定位过程，就是哈希表法和 Floyd 判圈算法的核心差异所在。

2. 哈希表解法：先解决，再优化

2.1 思路与 Java 实现

哈希表法是最符合直觉的解法。从 head 开始遍历链表，每经过一个节点，就把这个节点对象存进 HashSet。如果当前节点已经存在，说明它被访问过第二次，那么它就是入环点，直接返回。遍历到 null 都还没遇到重复节点，就说明链表无环，返回 null。

这里有个关键细节：集合里存的是节点对象本身，不是节点值。力扣的 ListNode 类没有重写 equals 和 hashCode，所以 HashSet 判断是否包含某个节点时，走的是默认的引用比较逻辑。同一个节点对象再次出现时，contains(cur) 就一定为 true。这对链表中存在相同数值的节点来说至关重要，因为哪怕两个节点的 val 都是 2，只要它们不是同一个对象，就不会被误判为环。

代码如下：

java复制public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        ListNode cur = head;
        while (cur != null) {
            if (seen.contains(cur)) {
                return cur;
            }
            seen.add(cur);
            cur = cur.next;
        }
        return null;
    }
}

这段代码的核心逻辑就是：首次重复访问的节点就是环入口。为什么这个结论成立？因为链表是从 head 一路沿着 next 前进的，进入环之前的所有节点都只能被访问一次；一旦进入环，绕完一圈碰到的一定是那个环入口节点。所以第一个被 contains 命中的节点，必然就是环的起始位置。

2.2 时间与空间复杂度

哈希表法的时间复杂度是 O(n)，空间复杂度也是 O(n)。在链表很长的情况下，额外占用的内存和链表长度线性相关。如果面试题没有额外限制，这个方法是最稳的，因为它的正确性非常直白，不需要推导数学公式，也不容易写错边界。

但很多公司在考察这道题的时候，会紧接着追问一句：能不能不用额外空间？这时候哈希表法就变得不够用了。不是因为它不正确，而是因为它的空间复杂度不满足优化预期。面试官真正想看的，往往是你能否在 O(1) 空间里完成同样的任务。

2.3 哈希表法的三个坑

第一个坑是拿节点值当判断依据。有人图省事，用 Set<Integer> 存数字，遍历时判断当前节点的 val 是否出现过。这在节点值互不相同的测试用例里碰巧能过，但一旦出现两个不同节点持有相同值的情况，就会产生误判，直接返回错误节点。

第二个坑是试图修改链表结构来标记节点。比如遍历时将访问过的节点 next 指向 null，或者指向一个哨兵节点。这种写法虽然在部分测试用例上能通过，但会破坏传入链表的原始结构，工程上不可接受，面试中也会被认定为“小聪明”，不建议这么干。

第三个坑是忽略 ListNode 的引用语义。HashSet<ListNode> 判断的是对象引用，这本身没问题，但如果你换成 HashMap<Integer, ListNode> 之类的结构，却仍期望通过值去查环，逻辑上就走偏了。哈希表法要想写得干净，只存节点对象就行，不要加额外逻辑。

3. Floyd 判圈算法：从相遇点到入口的数学推导

3.1 第一阶段：快慢指针找相遇点

Floyd 判圈算法又叫龟兔赛跑算法，核心思路是用两个速度不同的指针去遍历链表。慢指针 slow 每次走一步，快指针 fast 每次走两步。如果链表没有环，fast 会先一步碰到 null，循环结束，返回 null。如果有环，fast 和 slow 都会进入环内，由于速度差为 1，fast 在环里绕圈时终究会追上 slow。

注意循环条件要写成 while (fast != null && fast.next != null)。因为 fast 每次要移动两步，如果不提前判断 fast.next，在链表末尾时很容易出现空指针异常。这在链表无环的情况下尤其重要，属于边界处理的关键细节。

当 fast == slow 时，第一阶段结束。此时两个指针停下的位置一定是环内某个节点，但就像前面说的，它不是环入口。这一步只能得出“链表有环”的结论。

3.2 第二阶段：为什么同速前进会在入口相遇

第二阶段是 Floyd 判圈算法的精髓，也是很多面试官喜欢追问的地方。从相遇点开始，让一个指针从 head 重新出发，另一个指针停留在相遇点，两个指针每次各走一步，它们会再次相遇，而这次相遇的位置就是环入口。

要理解为什么，需要引入三个变量。设入环前链表的长度为 a，也就是从 head 到环入口需要走 a 步；环的长度为 L；慢指针从进入环开始，沿着 next 方向再走 b 步到达相遇点。那么慢指针从 head 到相遇点一共走了 a + b 步。快指针速度是慢指针的两倍，所以它走了 2(a + b) 步。

快指针比慢指针多走的部分，一定是在环里绕的整圈数。设多绕了 k 圈，就有：

text复制2(a + b) - (a + b) = kL
a + b = kL

这个式子非常关键。它说明从 head 到相遇点的总距离，恰好是环长度的整数倍。

接下来看第二阶段。从相遇点继续前进 L - b 步，可以回到环入口。而由于 a + b = kL，可以得到：

text复制a = kL - b

也就是说，从相遇点再走 a 步，等价于先绕 k 圈回到相遇点，然后再前进 L - b 步，最终落点正好是环入口。所以当某个指针从 head 出发走 a 步抵达入口时，另一个从相遇点出发的指针也走 a 步抵达入口，两者必然在同一位置相遇。

用前面的例子验证一下：[3,2,0,-4] 中，入环前长度 a = 1，环长度 L = 3，慢指针入环后走到相遇点需要 b = 2 步。此时 a + b = 3 = L，而从相遇点 -4 再走 1 步，正好回到 2，也就是入环点。

3.3 为什么一定是速度差为 1

很多初学者会问，快指针为什么非走两步不可，走三步行不行？这背后其实有严格的数学原因。Floyd 判圈算法的证明依赖“快指针比慢指针多走的路程是环长度的整数倍”这一前提，而速度差为 1 时，这个关系最干净。

更重要的是，速度差为 1 时，进入环后每移动一轮，快指针就比慢指针多追近一步。由于环长有限，最多走 L 轮，两者必然会相遇。如果快指针一次走三步，速度差就变成 2，快指针可能直接从慢指针头顶跳过去，相遇的时机变得不确定，推导中的同余关系也会被破坏。所以两倍的快慢速差并不是随意设定，而是保证算法正确性的最小配置。

4. Java 完整实现与测试

4.1 可直接运行的完整代码

下面是一份完整的 Java 实现，包含了力扣所需的 Solution 类，以及本地自测时需要的链表构造工具函数。把这段代码复制到本地 IDE，可以直接运行验证。

java复制import java.util.HashSet;
import java.util.Set;

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

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                ListNode p = head;
                ListNode q = slow;
                while (p != q) {
                    p = p.next;
                    q = q.next;
                }
                return p;
            }
        }
        return null;
    }

    // 根据数组值构建链表，并把尾节点指向下标 pos 处的节点
    public static ListNode buildList(int[] values, int pos) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        ListNode target = null;
        for (int i = 0; i < values.length; i++) {
            cur.next = new ListNode(values[i]);
            cur = cur.next;
            if (i == pos) {
                target = cur;
            }
        }
        if (target != null) {
            cur.next = target;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] values1 = {3, 2, 0, -4};
        ListNode head1 = buildList(values1, 1);
        ListNode entry1 = solution.detectCycle(head1);
        System.out.println(entry1 == null ? "null" : entry1.val); // 期望 2

        int[] values2 = {1, 2, 3, 4};
        ListNode head2 = buildList(values2, -1);
        ListNode entry2 = solution.detectCycle(head2);
        System.out.println(entry2 == null ? "null" : entry2.val); // 期望 null
    }
}

代码里第二阶段的写法很典型：p 从 head 出发，q 从相遇点出发，两个指针同步前移，直到它们相等。相等条件成立时，p 就是环入口节点。这个循环不需要额外的终止条件，因为数学上已经证明它们必定在入口处碰头。

4.2 测试用例设计清单

我平时自测这类链表题，习惯把边界情况都覆盖一遍，防止代码只在标准示例上正确。针对环形链表 II，可以设计下面几组用例：

头节点就是入口这个用例容易被忽略。链表只有一个节点 1，尾节点指向自己，此时快慢指针从同一个点出发，第一次循环就满足 slow == fast，第二阶段两个指针都从 head 出发，直接返回节点 1。这组用例能测试代码在极小环下是否产生空指针。

4.3 边界与调试技巧

本地调试环形链表时有一个烦恼：如果直接用 while (cur != null) 循环去打印链表，遇到有环的情况会死循环，程序直接卡住。我自己的做法是写一个带保护条件的打印函数，一边遍历一边把访问过的节点放进集合，走到重复节点时停止，并标记出入口位置。这样既能看清链表结构，又不会把 IDE 卡死。

还有一个经验是，调试第二阶段时特别容易犯一个错：有人会把 p 的初始位置写成 fast 或 slow，导致两个指针从同一个点出发，一上来就相等，返回错误的相遇点。记住，p 必须从 head 开始，q 从相遇点开始，这两者的初始位置不能搞混。这个错误在简单示例里很容易暴露，但遇到某些恰好让入口等于相遇点的用例时反而可能被掩盖，所以最好在多个用例上都跑一遍。

5. 面试追问、变种题与工程外延

5.1 面试官高频追问参考

面试官拿到这道题之后，通常不会只满足于你写出一份可以通过的代码。他们更喜欢顺着你的解法往下挖，直到确认你真正理解原理，而不是背了模板。以下是我整理的高频追问和参考思路。

回答“怎么求环的长度”时，可以直接从相遇点开始，固定一个指针不动，另一个指针每次走一步，再次回到相遇点时走过的步数就是环长。这一步其实也反过来验证了前面推导的正确性，因为你在代码里已经找到了相遇点，环长的计算只是多走一圈的计数问题。

5.2 环形链表同源的双指针题

“环形链表”这类题目有一个共同的思想：通过快慢指针的位移差来定位链表中的特殊位置。除了本道题之外，还有几个高频题也依赖这个套路。

其中最简单的是判断链表是否有环，也就是环形链表 I，只需要跑第一阶段，碰到相遇返回 true，跑到 null 返回 false。然后是找链表中点，快指针走两步，慢指针走一步，当快指针到末尾时，慢指针正好在中点位置。这个技巧在归并排序链表时非常常用。还有找链表中倒数第 k 个节点，快指针先走 k 步，然后快慢指针同速前进，快指针到末尾时慢指针就是倒数第 k 个节点。

把这些题放在一起看，你会发现双指针不是一招鲜，而是一套处理链表问题的通用方法。区别只在于位移差、初始位置、相遇条件这些参数的组合方式。

顺便提一句，“快乐数”这道题也用了 Floyd 判圈算法的思想。把每个数字的下一个数字看作链表的 next，如果一个数是快乐数，最终会到达 1，相当于进入一个“无环”链表；如果不是快乐数，就会出现循环，而循环会被快慢指针检测出来。这种跨题迁移能帮你建立更完整的算法认知。

5.3 工程中的循环检测思路

算法的价值不只是过题。在真实工程里，循环引用检测、依赖关系环检测、消息队列重复消费判断，都和处理链表环的问题有相通之处。

我自己的经验是：如果内存和数据结构允许，工程中更偏向用哈希集合来记录已经处理过的对象，因为直观、稳定、不容易受数学推导影响。但如果遇到状态空间极大且不能额外分配内存的场景，类似 Floyd 判圈算法的 O(1) 空间思路就很有参考价值。理解两种方案的取舍，比死记某一题的解法更有意义。

最后再分享一点我自己的体会

我第一次接触这道题的时候，其实也不太理解为什么第二阶段要把一个指针放回 head。后来我在草稿纸上画了一堆链表的箭头，把 a、L、b 代进公式反复推，才算真正想通。从那以后，只要遇到环相关的问题，我都会先设变量、画图、列关系式，再动笔写代码。

如果你现在也被这个证明卡住，不妨换一个具体的数字例子，一步步手动模拟快慢指针的移动过程。这个过程虽然看起来慢，但比直接背结论要扎实得多。等你把 a + b = kL 这个式子吃透了，再回来看第二阶段的代码，就会有一种“原来就这么简单”的感觉。

一个小建议：刷这道题的时候，别再满足于“抄代码抄过了”。试着合上题解，自己在本地把哈希表法和 Floyd 判圈法各写一遍，再用不同的测试用例跑一跑。能讲清楚原理的代码，才是面试里真正拿得出手的答案。