环形链表II详解：快慢指针找环入口的Floyd算法与Java实现

1. 从“判圈”到“找入口”这道题到底难在哪里我第一次在 LeetCode 热题 100 里刷到环形链表 II 的时候心里其实是有点轻视的。毕竟前面刚做完环形链表 I快慢指针判断有没有环代码十几行就结束了感觉已经拿捏了链表环类问题。结果点开环形链表 II 一看题目从“判断有没有环”变成了“找出环的入口节点”我就愣住了入口节点怎么定位两个指针相遇的位置明明已经在环内了怎么确定它是不是入口如果不是又该怎么走到入口先说清楚题目本身。给定一个链表的头节点 head如果链表中存在环则返回入环的第一个节点如果没有环则返回 null。注意这里不能修改链表结构也不能额外记录每个节点的下标和地址题目要求的是一个函数式解法而且常常在面试里追问“你能否只用 O(1) 空间解决”如果你第一次看到这题大概率会有两种反应。第一种是我直接遍历链表用一个集合记录访问过的节点第一次遇到重复节点就是入口。这个思路完全正确时间复杂度 O(n)空间复杂度 O(n)几分钟就能写出来。第二种是我尝试用快慢指针但发现两个指针在环里相遇之后那个相遇点不一定是入口然后就卡住了。我后来复盘了一下环形链表 II 真正让人难受的地方是判断有没有环是一个“布尔型问题”你只要知道环存在就行找入口是一个“位置型问题”你必须证明某个点就是入口而不能靠猜。快慢指针确实能在环内相遇但这个相遇点只是“环内某个点”离入口还差一段距离。要算出这段距离就得理解 Floyd 判圈算法背后那个经典的数学推导。这篇文章我打算用比较完整的篇幅把环形链表 II 从哈希表到 Floyd 判圈算法拆开讲一遍。适合正在刷 LeetCode 热题 100 的朋友也适合准备面试前想把这个考点彻底搞懂的人。我不会只给代码而是会把我理解的推导过程、Java 实现细节、测试用例构造方式以及面试中被追问时怎么应对一次性讲清楚。2. 哈希表是基础方案正确但不够优雅拿到这道题最先想到的方案就是哈希表。核心逻辑很简单从头节点开始遍历每经过一个节点就把它放进一个集合在放入之前先查一下集合里有没有这个节点。如果有说明这个节点被访问过两次而它一定是环的入口如果遍历到了 null说明链表无环。这个逻辑为什么成立因为链表的每个节点在内存里都是一个独立的对象如果存在环那么环入口节点必然会被访问两次一次是第一次到达入口时一次是绕完一圈回到入口时。而环内其他节点也都会被访问两次但第一个被重复访问的节点一定就是入口节点。这里的关键是“第一次重复”所以只要我们按遍历顺序去查第一次命中的重复节点就是答案。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) { SetListNode seen new HashSet(); ListNode cur head; while (cur ! null) { if (seen.contains(cur)) { return cur; } seen.add(cur); cur cur.next; } return null; } }这里有一个非常容易被新手踩的坑判断重复时不要用 cur.val 去比较而要比较节点对象本身。因为链表里可能出现两个不同节点拥有相同 val 的情况比如一条无环链表 [1, 2, 2, 1]你如果按值判断一定会误判成有环。哪怕测试用例里不出现重复值我依然建议养成用对象引用判断的习惯LeetCode 的判题系统也是按节点对象来判断环的。哈希表方案的时间复杂度和空间复杂度都是 O(n)。在 n 很小时比如几千个节点这个方案用起来完全没问题。但面试官通常不会让你这么轻松过关紧接着就会问能不能把空间复杂度降到 O(1)这就是 Floyd 判圈算法出场的时机。不过我也想说一句公道话哈希表不是错误的方案它是建立直觉的起点。它告诉我们一个最朴素的道理——环的存在意味着某个节点会被重复访问环的入口就是第一个被重复访问的节点。有了这个认知后面理解 Floyd 算法会顺很多。3. Floyd 判圈先是操作后是直觉Floyd 判圈算法的思路可能很多人已经在环形链表 I 里见过了一个慢指针 slow 每次走一步一个快指针 fast 每次走两步如果链表有环它们一定会在环内相遇。但这里的实现要注意一点环形链表 II 不是找到相遇就结束了而是要先找到相遇点再用相遇点去反推入口。所以我把 Floyd 算法拆成两个阶段第一阶段检测是否有环并找到第一个相遇点。第二阶段从头节点和相遇点同时以步长 1 前进这两个指针相遇的位置就是环的入口。第二阶段的结论非常神奇但也非常需要证明。先看第一阶段的标准 Java 写法public ListNode detectCycle(ListNode head) { if (head 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) { // 找到了相遇点跳出循环 break; } } // 没有环的情况 if (fast null || fast.next null) { return null; } ListNode p head; ListNode q slow; while (p ! q) { p p.next; q q.next; } return p; }在慢指针进入环之前两个指针都在链表“直线段”上跑这时它们不可能相遇因为 fast 始终在 slow 前面。一旦 slow 进入环情况就变了fast 此时已经在环里了它可能绕了不止一圈但两人最终会在环内碰上。为什么一定会在环内碰上假设 slow 刚进入环的那一刻fast 在环内某个位置两人之间沿着环的前进方向有一段距离。由于 slow 速度为 1fast 速度为 2每一轮循环过去fast 相对 slow 的距离就会缩短 1。所以无论这段初始距离有多大在有限步数内fast 一定会“追上”slow也就是从后面绕一圈赶上它两人在同一个节点相遇。我用一个生活化的类比来帮助理解想象操场上跑步A 跑得慢B 跑得快B 本来就在 A 前面的某个位置。因为 B 比 A 快两人的距离每秒缩短 1当距离被缩短到 0 时两人就并肩了。注意这里“距离缩短”是相对速度决定的不是绝对位置决定的。所以不需要考虑 fast 绕了多少圈反正它总会追上 slow。我当年第一次看完这个证明觉得逻辑没问题但有个地方想了很久为什么 fast 和 slow 在环内相遇的点就能用来找入口相遇点到底和入口有什么数量关系这就是下一节要讲的数学推导了。4. 入口点推导一个等式拉开真相Floyd 判圈算法最有魅力的部分其实是它的数学推导。很多刷题的人只记住了“相遇后从头走一个指针再同步走就是入口”但面试官一旦追问“你为什么这么做”如果答不上来这道题就大打折扣。我们设几个变量a链表头节点到环入口的距离即入口前的节点数。b环入口到 fast 与 slow 第一次相遇点的距离。c环的周长。nfast 从进入环到第一次与 slow 相遇期间比 slow 多跑的整圈数。当 slow 和 fast 第一次相遇时slow 走过的路程是 a bfast 走过的路程是 a b n * c。因为 fast 的速度是 slow 的两倍两者运动时间相同所以 fast 的路程是 slow 路程的两倍2 * (a b) a b n * c化简得到a b n * c也就是说a n * c - b这个式子就是整个算法的核心。看着有点抽象我来解释一下从头节点走到入口的距离 a等于“环绕了几整圈再往回退 b 个节点”的距离。也就是说如果你从相遇点继续沿链表往前走了距离 c - b你会回到相遇点而如果我们从相遇点出发沿着链表前进 c - b再绕过 n-1 整圈其实也能到达入口。更直观的说法是从相遇点往前走一步绕完剩下的弧长能回到相遇点但从相遇点出发走到入口的“最短距离”是 c - b而 a 恰好等于 n * c - b。因此从相遇点出发沿着链表不断走走 c - b 步能到达入口如果 a 比 c - b 大多的部分正好是整数圈不影响最终落点。基于这个结论我们安排两个指针一个从 head 出发一个从相遇点出发每次各走一步。当第一个指针走了 a 步到达入口时第二个指针从相遇点走了 a 步也就是走了 c - b 步再加若干整圈它正好也在入口。于是两个指针在入口相遇此时返回第一个指针指向的节点就是答案。这个推导里有一个细节值得单独提出来n 不一定是 1。很多人做完环形链表 I习惯性地以为 fast 最多比 slow 多跑一圈就会相遇。在环很长、直线段很长、或者环很短的极端情况下n 可能大于 1。举个例子如果入口前的直线部分 a 5环周长 c 3相遇时的 b 可能是 1。代入公式a b 6n 2fast 比 slow 多跑了两整圈。所以遇到这种结构时第二阶段两个指针要走不少步才能同时到达入口但结论依然成立。理解 n 可以是任意正整数能帮你摆脱对“一圈相遇”的错误刻板印象。我建议你把这段推导写在自己的笔记里不要只记结论。因为面试时你很可能被要求现场讲证明而照着公式说一遍和真正理解之后再讲一遍效果完全不同。5. Java 完整实现与自测用例的细微之处理论讲完了来看一个完整的 Java 实现。这一节我会把测试辅助方法也写出来方便你在本地跑一遍真正看到效果。因为 LeetCode 上的输入格式是 [3,2,0,-4] 和 pos1这表示数组对应节点值pos 表示尾节点的 next 指向第几个节点如果 pos 为 -1则表示无环。本地测试时需要自己构造这样的链表。先定义节点类class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } }然后写一个构造函数根据数组和 pos 生成链表。为了代码简洁我用一个 dummy 节点来串联所有新节点最后再根据 pos 找到对应节点并让尾节点指向它static ListNode buildList(int[] values, int pos) { ListNode dummy new ListNode(0); ListNode cur dummy; ListNode cycleNode null; for (int i 0; i values.length; i) { cur.next new ListNode(values[i]); cur cur.next; if (i pos) { cycleNode cur; } } if (pos 0) { cur.next cycleNode; } return dummy.next; }这里有一个很容易忽略的边界情况如果 values 数组只有一个节点同时 pos 又是 0那么这个节点就是自环结构也就是它自己指向自己。buildList 方法依然能正确工作因为 cycleNode 指向了当前节点cur.next 也重新指向它。测试 Floyd 算法时这种单节点自环是很好的边界测试。主方法我建议写成两部分这样代码更清晰第一段双指针找相遇点第二段同步前进找入口。public class Solution { public ListNode detectCycle(ListNode head) { if (head null) { return null; } ListNode slow head; ListNode fast head; ListNode meet null; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { meet slow; break; } } if (meet null) { return null; } ListNode p head; ListNode q meet; while (p ! q) { p p.next; q q.next; } return p; } }注意第二阶段循环的条件是 p ! q所以当 p 和 q 都是环入口节点时循环终止直接返回 p 即可。这里不需要额外判断 p 是否为 null因为既然第一步证明了有环那么第二阶段的指针无论怎么走都不会走到 null它们一定会在环内相遇。然后写一个 main 方法冗余几个测试用例来验证public static void main(String[] args) { Solution solution new Solution(); // 测试1链表 [3,2,0,-4]pos1期望返回节点2 ListNode list1 buildList(new int[]{3, 2, 0, -4}, 1); ListNode result1 solution.detectCycle(list1); System.out.println(Test1: (result1 ! null ? result1.val : null)); // 期望输出2 // 测试2链表 [1,2]pos0期望返回节点1 ListNode list2 buildList(new int[]{1, 2}, 0); ListNode result2 solution.detectCycle(list2); System.out.println(Test2: (result2 ! null ? result2.val : null)); // 期望输出1 // 测试3链表 [1]pos-1无环期望返回null ListNode list3 buildList(new int[]{1}, -1); ListNode result3 solution.detectCycle(list3); System.out.println(Test3: (result3 ! null ? result3.val : null)); // 期望输出null // 测试4单节点自环pos0期望返回节点1 ListNode list4 buildList(new int[]{1}, 0); ListNode result4 solution.detectCycle(list4); System.out.println(Test4: (result4 ! null ? result4.val : null)); // 期望输出1 }如果你本地跑这四个用例会发现 Test1 输出 2Test2 输出 1Test3 输出 nullTest4 输出 1。这说明算法在不同形态下都能正确工作。我想额外提醒的是如果面试时要求你写代码不一定非要像我这样把 buildList 写出来LeetCode 环境里也不需要写测试代码。但你在本地练习时一定要学会自己构造循环链表否则你很难真正验证自己的实现是否可靠。很多初学者只靠 LeetCode 在线判题漏掉了本地构造数据和调试的过程这会导致遇到边界用例时心里没底。6. 变体、面试追问和实战中的几个小提醒环形链表 II 在热题 100 里的位置比较特殊它不像那些“背模板”的动态规划题而更像是一道需要完整数学推理的链表题。面试中围绕它进行追问通常有这么几个方向。第一个追问是如果只判断有没有环怎么写这时候你只需要用到第一阶段的快慢指针即可不需要后面的数学推导。没有环就返回 null有环就返回 true。这个版本我建议单独记忆因为和环形链表 II 的完整版代码结构很像但返回类型不同很多人会混淆。第二个追问是为什么 fast 每次走两步不是走三步或者四步这个问题的标准回答是步长为 2 时fast 相对 slow 的速度差为 1保证了“每一步追赶 1 个节点距离”因此在高频相遇时间上不会跳过 slow。如果 fast 走 3 步相对速度差是 2当两个节点之间的距离刚好为奇数时fast 可能从 slow 旁边“跳过去”导致理论上能相遇的实现却因为步长问题永远碰不到。这个问题在面试里属于加分项知道原理会让面试官觉得你不是在背解法。第三个追问是如果链表节点数很大比如一亿个节点哈希表还可行吗答案是空间开销太大不稳定所以必须回到 O(1) 空间方案。这时候你如果能顺畅地把第四节的数学推导复述出来基本就能过这一关。第四个追问是如果要返回的是环的长度而不是入口节点怎么办这个问题其实很简单在快慢指针相遇后让其中一个指针原地不动另一个指针每次走一步绕一圈回到相遇点时走过的步数就是环长。本质上是利用相遇点一定在环内这一事实。这个变体在一些公司的笔试里出现过建议顺手练一下。再说说实际工程中对这个算法的应用。Floyd 判圈算法不只是 LeetCode 题它在检测循环依赖、检测状态机中的死循环、解决“链表类结构中的闭环”问题时都很实用。比如某些配置系统里的对象引用链如果出现循环引用就会导致序列化或内存分析工具卡死这时候就可以用类似思路快速检测。我见过有人把快慢指针写进一个数据校验工具里专门用来检查配置拓扑中是否存在循环效果很好。最后写一个很实际的小提醒在 Java 里面判断两个节点是否相等永远用 而不是 equals。因为链表节点的实体是对象引用即使两个不同节点的 val 相同它们也不是同一个对象。LeetCode 的测试数据允许不同节点的 val 重复所以如果误用 val 判断会产生严重的误判。这个坑我在给同学讲代码时反复强调过因为真的有人在这里栽过跟头。我个人在实际刷题中的体会是环形链表 II 这道题正确代码写出来并不难真正拉开差距的是对证明过程的理解。把 a、b、c、n 这套符号写一遍推导比单纯抄十遍代码更有用。面试时如果能把推导讲清楚同时给出 O(1) 空间的 Java 实现这道题基本就是稳稳拿下了。如果你后面刷到其他需要用数学推导的题型比如找重复数、猜数字大小、矩阵搜索类问题也可以试着用这种“先直观理解、再符号化推导、最后代码落地”的顺序去学你会发现记忆负担小很多。