说实话刷到 Hot100 第 22 题的时候我心里是有点轻视的——环形链表这题名听着太基础了第一反应就是“哈希表嘛遍历一遍记个地址就行”。但后来在一次模拟面试里被面试官追问了一句“不用额外空间怎么做”我当场愣住才意识到这题藏着一个特别经典的快慢指针思想也就是 Floyd 判圈算法。后来我把两种解法、边界条件、证明过程甚至扩展题 142 都完整啃了一遍才发现这题虽然标着 Easy考点密度却一点都不低。这篇就把我完整的做题过程和思考整理出来包含完整代码、复杂度分析、面试现场怎么讲、以及大概率会被追问的找环入口推导。无论你是刚入门算法题的新手还是准备跳槽面试需要快速过 Hot100 的老手这篇应该都能给你省不少时间。1. 题目卡点和核心思路拆解1.1 题目到底在考什么题目本身就一句话给定一个链表的头节点 head判断链表中是否有环。如果有环返回 true没有环返回 false。很多人第一眼觉得这题简单但它真正考的东西其实很具体链表节点的存储特点和指针追及问题的数学直觉。链表在内存里是一串节点每个节点有一个 next 指针指向下一个节点地址。如果链表中存在环就意味着某个节点的 next 指针指向了之前已经出现过的某个节点从那里开始遍历会永远循环下去形成一个封闭的环。这里有个容易踩的坑环的存在跟节点值完全无关判断条件必须基于节点的引用内存地址而不是节点上存的值。两个不同节点可以有相同的 val这时如果用值去判重就会得到错误结果。LeetCode 上给的链表节点结构大概是这样class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } }题目要求返回布尔值但实际面试时面试官往往不会停留在“会不会做”这个层面而是会追问“为什么快慢指针一定相遇”“空间复杂度能不能做到 O(1)”“能不能找环的入口”。这题就像一个入口背后牵扯出一整套链表问题的解题框架。1.2 先说结论两种解法一个玩空间一个玩时间这题的标准解法就两个方向理解它们的差异比背代码重要得多哈希表法遍历链表每经过一个节点就把它的引用存进一个 Set如果遇到某个节点已经在 Set 里说明存在环。时间复杂度是 O(n)空间复杂度也是 O(n)。快慢指针法维护两个指针slow 每次走一步fast 每次走两步。如果链表没有环fast 会先到达末尾如果有环fast 和 slow 一定会在环内某一处相遇。时间复杂度 O(n)空间复杂度 O(1)。两种方法的取舍很清楚哈希表法直观、代码简单、不容易出错快慢指针法空间更优而且是面试官更想听到的解法。大部分 LeetCode 官方题解以及各大厂面试的标准答案都会默认你会快慢指针。所以哈希表应该是你脑中第一个跳出来的思路但快慢指针才是你真正要写进简历的解法。1.3 一个重要的前置心智模型在写代码之前我建议你先建立一个心智模型链表不是一条“线”而是一串内存地址的链式结构。当你遍历链表时指针是在“节点地址”之间移动而不是在“值”之间移动。这个模型有助于你理解为什么哈希表存的是节点引用以及为什么快慢指针的相遇判断可以精确到地址相同。从这个角度去看环形链表本质上是一个“指针是否会回到已访问地址”的问题。哈希表法用额外的空间记录“已访问地址”快慢指针法则利用“不同速度在封闭环内必然追及”的数学性质省掉了记录空间。后面的所有代码都是围绕这两个视角展开的。2. 解法一哈希表最简单也最容易想到2.1 哈希表解法原理哈希表法的思路非常符合直觉。你可以想象成走迷宫的时候每到一个路口就把门牌号记在本子上。如果走着走着发现当前门牌号在本子上已经出现过那就说明你绕回到了已经走过的位置前面是一个死循环。具体到链表就是初始化一个空的哈希集合从 head 开始遍历每到一个节点就检查这个节点的引用是否已经在集合里。如果在直接返回 true如果不在就把节点引用加进集合然后继续走。如果遍历到 null说明链表走完了也没遇到重复节点返回 false。这里我再强调一次集合里存的是节点对象本身的引用。Java 的 HashSet 会调用对象的 hashCode 和 equals 方法而 ListNode 默认的 hashCode 是基于内存地址的所以存引用天然能区分不同节点。如果你自作聪明去存 val一旦链表里有重复值结果就是错的。2.2 Java 代码实现带注释走读public boolean hasCycle(ListNode head) { // 记录已经访问过的节点引用 SetListNode seen new HashSet(); ListNode p head; while (p ! null) { // 如果当前节点之前出现过说明存在环 if (seen.contains(p)) { return true; } seen.add(p); p p.next; } // 遍历到链表终点说明没有环 return false; }这段代码逻辑非常直白唯一的注意点是SetListNode的泛型类型必须是 ListNode而不是 Integer。只要节点是同一个对象哈希集合就能识别出来。2.3 复杂度与隐藏的问题哈希表法的复杂度分析很简单时间复杂度O(n)最坏情况下需要遍历所有节点才得出结果。空间复杂度O(n)最坏情况下所有节点都被放进集合占用与节点数成正比的内存。表面上看起来这个解法“稳”但问题也就出在空间上。当链表长度达到几万甚至几十万节点时额外开一个 HashSet 的内存开销并不小。而且在算法面试里凡是题目考查“链表 环”这个组合面试官基本都会要求你给出 O(1) 空间的方案。如果一上来就只会哈希表很容易被判定为“思路比较基础”。2.4 什么时候该放弃哈希表优先考虑双指针我的建议是如果面试官没有提任何限制条件哈希表法是很好的第一回答因为它最直观能体现你能够快速给出一个正确解法。但当面试官追问“能不能优化空间复杂度”时你就要立刻意识到他期待的答案是快慢指针。这时候就不要再去纠结哈希表的常数优化了直接转向快慢指针才是正路。还有一种情况也该优先用快慢指针当链表长度很大、内存紧张或者你在嵌入式、底层系统中处理链表O(n) 的空间开销可能是不可接受的。工程上的链表通常不会无限长但面试考察的本质是你在资源受限时的取舍能力。所以快慢指针不是“炫技”而是真正有工程意义的解法。3. 解法二快慢指针真正该学的解法3.1 Floyd 判圈算法是怎么想到的快慢指针有一个正式的名字Floyd 判圈算法Floyds Cycle Detection。它的思想来源特别生活化在一个环形跑道上如果两个人同时出发一个人跑得快、一个人跑得慢那么跑得快的人最终会从后面追上跑得慢的人。在一条笔直跑道上跑得快的人只会先到终点永远不会被追上。把链表类比成跑道唯一的问题是快指针必须每次比慢指针多走一步也就是 fast 每次走两步、slow 每次走一步。这样才能保证两者在环内相对速度是 1从而在数学上一定能追上。如果你让 fast 走三步、四步虽然有时候也能相遇但这个“有时候”就是最大的风险后面第 5 节我会专门讲这个问题。3.2 证明为什么两步一追就一定能碰面这里需要一点简单的数学证明面试的时候能讲出来是加分的。为了方便理解我把证明拆成两步第一步如果链表没有环fast 每次走两步它会比 slow 更快到达 null。所以 while 循环会在 fast 或者 fast.next 为 null 时终止返回 false。这很好理解。第二步如果链表有环slow 进入环之后fast 一定已经在环里了因为 fast 跑得快可能已经绕了好几圈。此时把环看成一条环形跑道fast 在 slow 的“前方或者后方某个位置”两者的相对距离记为 d。由于 fast 比 slow 每秒多走一步所以每过一个单位时间两者的距离 d 就会减少 1。当 d 减少到 0 时两者就在同一个节点上相遇。因为每次减少的是 1一个正整数总能在有限步内归零所以相遇一定发生。这个证明就是 Floyd 判圈算法的核心。面试时你只要把这个逻辑说清楚面试官基本就会认可你的理解。3.3 Java 代码实现带注释走读public boolean hasCycle(ListNode head) { // 空链表或只有一个节点不可能成环 if (head null || head.next null) { return false; } ListNode slow head; ListNode fast head; // fast 每次走两步所以要保证 fast 和 fast.next 都不为 null while (fast ! null fast.next ! null) { slow slow.next; // 慢指针走一步 fast fast.next.next; // 快指针走两步 // 地址相同说明追上了存在环 if (slow fast) { return true; } } // fast 走到链表末端无环 return false; }这段代码有几个关键点要说一下。循环条件是fast ! null fast.next ! null因为 fast 在循环体内要访问fast.next.next如果fast.next本身就是 null就会出现空指针异常。另外slow 和 fast 都初始化为 head然后先移动、后判断这个顺序也很有讲究我们第 5 节会单独讲。3.4 复杂度分析与几个小细节快慢指针的时间复杂度是 O(n)空间复杂度是 O(1)。很多资料直接写“时间复杂度 O(n)”但完整说法是链表无环时fast 遍历到末尾耗时约 n/2 步链表有环时slow 进入环后最多在环内走不到一圈就会被 fast 追上所以总步数仍然是 O(n)。这里的“最多走不到一圈”可以用一个直觉解释fast 相对于 slow 每秒缩短 1 单位距离而两者初始距离最多不超过环长 L所以追及所需时间不超过 L。面试时可以说“时间复杂度是线性的具体常数跟环的位置有关但整体不会超过 O(n)”。还有一个细节快慢指针在环内的相遇点一定在环的入口之后不会在入口之前。这一点在后续推导环入口时很关键先留个印象。4. 实操过程从读题到提交通过的完整复盘4.1 边界条件怎么处理这题虽然简单但边界条件处理不好照样会出问题我梳理了三个最容易踩的空链表head 为 null没有节点必然无环。直接返回 false不需要进入循环。只有一个节点head.next 为 null也必然无环。同样直接返回 false。单节点自环head.next 指向自身这种情况下链表只有一个节点但它确实是一个环。此时快慢指针都从 head 出发slow 走一步还是回到 headfast 走两步也会回到 head两者在第二轮相遇返回 true。前两个边界条件我习惯在函数开头统一处理if (head null || head.next null) { return false; }这样写既简洁又能避免后面的空指针问题。单节点自环的情况则不需要特殊处理快慢指针代码本身就覆盖了。4.2 完整测试用例设计写算法题不能只满足于“过了 LeetCode 的样例”我一般会在本地或者脑子里过一套完整的测试用例确保边界覆盖到位。下面这个表是我自己常用的测试矩阵用例链表结构预期结果空链表head nullfalse单节点无环1 - nullfalse单节点自环1 - 自身true两个节点无环1 - 2 - nullfalse两个节点成环1 - 2 - 1自环true链尾指向中间1 - 2 - 3 - 4 - 2true链尾指向头节点1 - 2 - 3 - 1true长链表无环1 - 2 - ... - 10000 - nullfalse这套用例基本覆盖了所有分支空、单节点、多节点、环在头部、环在中间、自环、无环。写题时把这些情况在脑子里过一遍代码的健壮性会明显提高。4.3 Python 实现有什么不同国内不少读者用 Python 刷题Python 版本和 Java 的差别非常小重点在于判断引用相等时要用is而不是。在 Python 中可能会触发对象内容的比较而我们要的是地址判断所以必须用is。顺便给一个可以运行的版本def hasCycle(self, head: ListNode) - bool: if not head or not head.next: return False slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False这段代码在 LeetCode 上可以直接跑通。Python 的代码虽然简洁但面试手写时要注意类型标注不一定要写全重点是把逻辑讲清楚。我个人一般先写 Java 版本因为 Java 对空指针的约束更严格写的时候会下意识想清楚每一个next是否可能为 null反而更容易避免边界错误。4.4 面试现场如何一步步说清楚面试的时候建议按照下面这个顺序由浅入深地表达效果最好先说暴力解“首先我可以遍历链表把访问过的节点放进 HashSet如果遇到重复节点就有环。这样做时间 O(n)、空间 O(n)。”主动提出优化“题目如果要求空间 O(1)我可以用快慢指针慢指针走一步快指针走两步。如果没有环快的会先遇到 null如果有环两者最终在环内相遇。”补充正确性证明“因为快指针相对慢指针的速率为 1 步/单位时间每次追 1 个单位的距离所以有限步内必然追上。”提边界“空链表、单节点链表直接返回 false单节点自环的时候两个指针走完一轮会相遇。”写代码然后自己过一遍测试用例。这套表达方式的妙处在于不管面试官接下来追问什么你都已经把思路、证明、边界全部展示过了后续对话基本就在你的节奏里。我第一次模拟面试时只说了代码没有讲证明结果被追问“你怎么证明一定相遇”时卡住了。后来我把证明补上整个回答的完成度完全不一样。5. 常见问题与避坑踩过才懂的点5.1 快指针走三步行不行我劝你老实走两步这是我在学习过程中产生过的最大的疑问既然 fast 走两步能追上为什么不能走三步、四步这样不是更快吗实际测试下来走三步在部分情况下确实能相遇但无法保证在所有环形链表上都相遇。背后是数学上的同余问题。设环的长度为 L快指针每单位时间走 k 步慢指针走 1 步速度差 d k - 1。假设某一时刻两者的相对距离为 r那么二者相遇的数学条件是存在整数 t 使得 r d·t 能被 L 整除。这个同余方程等价于 d·t ≡ -r (mod L)有解的充要条件是 gcd(d, L) 能整除 r。标准解法中 d 1任何 r 都能被 1 整除所以一定相遇。而如果你让 fast 走三步d 2如果环长 L 是 4初始相对距离 r 是奇数gcd(2, 4) 2 无法整除 r则永远不可能相遇。所以面试时千万不要自作聪明写 fast fast.next.next.next。标准答案就是两步一步因为只有这个速度差能保证判断绝对正确。5.2 死循环和空指针是怎么出现的快慢指针写法有一个常见的隐藏 BUG先判断等于 head再移动。假设你把判断写成while (fast ! null fast.next ! null) { if (slow fast) { return true; } slow slow.next; fast fast.next.next; } return false;这个写法在普通无环链表上没问题但在单节点自环时初始 slow 和 fast 都等于 headwhile 循环一进去就直接命中slow fast返回 true结果某种程度上依然正确。真正的问题出在有环但入口不在 head 的链表上——初始判断的时候 slow 和 fast 都在 head这个判断并没有做错但会误导你忽略一个事实判断相遇应该放在移动之后。因为初始时两个指针本来就在同一个起点这个“相遇”毫无意义。更经典的错误是循环体内先判断fast.next.next而忘记检查fast.next是否为 null。如果链表长度是奇数fast 走到最后一个节点时fast.next为 null此时再去取fast.next.next就会抛 NullPointerException。所以必须把fast ! null fast.next ! null同时写在 while 条件里。5.3 哈希表法的隐性限制哈希表法也有一个容易忽略的点两个不同节点可能拥有相同的值所以集合里必须存节点引用。如果你误存了ListNode.val当链表中有两个值为 3 的不同节点时第二个就会被误判为“已经出现过”从而把无环链表判成有环。另外Java 的HashSetListNode是因为 ListNode 默认equals才达到正确语义的。如果你在真实工程里自定义了一个重写了 equals 的链表节点类用哈希表判环前就要想清楚这个 equals 是基于值还是引用。基于值的 equals 在这个场景下会让哈希表法失效。这也是我为什么强调“理解哈希表存的是引用”比记住代码更重要的原因。6. 进阶这题背后还能挖出什么6.1 变体题找环入口142 题原理推导Hot100 里紧接着就有一道关于环形链表的变体题142. 环形链表 II要求返回链表中环开始的节点。很多同学背下了代码但不理解为什么相遇后把一个指针放回头节点再同步走一次就能找到入口。这里我把推导写清楚建议收藏。设链表中 head 到环入口的距离为 a环入口到快慢指针相遇点的距离为 b相遇点到环入口的距离为 c环长为 L b c。慢指针从 head 到相遇点一共走了 a b 步。快指针速度是慢指针的 2 倍所以它走的距离是 2(a b)。同时快指针走的路程也可以写成a b kL其中 k 表示快指针在相遇前绕了 k 圈。于是有2(a b) a b kL进一步化简a b kL再代入 L b ca kL - b (k - 1)L c这个式子的含义是从 head 走到环入口的距离 a等于从相遇点继续走 c 步绕了 k-1 圈之后的距离。因此推导出解法第一次相遇后把一个指针放回 head另一个留在相遇点两者都以步长 1 移动再次相遇时的节点就是环入口。这个推导我建议你亲自在草稿纸上画一遍图半个月后都不会忘。面试现场能当场推导出来的候选人通常都能给面试官留下很好的印象。6.2 工程场景里的环形链表你可能觉得链表判环只是个面试题实际工程中用得不多。其实环形结构在系统设计里非常常见CPU 调度里的循环队列、网络数据包的环形缓冲区、某些缓存淘汰算法里的循环链表都是“链表 环”的形态。当这些结构出现异常比如某个 next 指针被错误地指回之前的位置就会导致死循环、CPU 占用飙升、服务卡死。我在定位线上问题时确实遇到过一次类似的现象某个消息队列消费者线程一直不退出日志刷个不停最终定位下来是队列的某个节点被错误改写了 next 指针形成了一个意外的环。那时候我才真切感受到判环不只是一个算法题它也是一种排查无限循环问题的通用思路。就算链表不大指针故障引发的服务异常也可能很严重掌握这个工具相当于给自己储备了一个应对循环问题的检测手段。另外不断轮询的 DNS 负载均衡、循环链表实现的进程调度等场景天然就需要能正确识别“这个环是我想要的还是异常产生的”。所以把快慢指针吃透对后面的系统设计面试也有帮助。6.3 一个刷题方法论的建议最后分享一个我自己刷题的方法凡是链表题一律先在纸上画图标出每个指针的位置变化再写代码。尤其是环形链表这种需要“动态追及”的题目光靠脑子想很容易漏边界画图之后每一步都很清楚。具体做法是画一条链表把 slow 和 fast 的当前位置用两个不同颜色的点标出来然后逐步推进模拟 3 到 5 步。你会直观地看到 fast 进入环、slow 后进入环、两者距离逐步缩短直到相遇的完整过程。这个习惯帮我解决的不只是 141 和 142还包括后面一大堆链表操作题比如反转链表、合并有序链表、删除倒数第 N 个节点。链表题本来就依赖空间想象多画图不会亏。第二点建议是不要只满足于“提交通过”。LeetCode 上通过这一题很容易代码也不长内核是快慢指针的理解和 142 的推导。这两个点才是这题真正的价值所在。如果你能顺手把相遇点、环入口、环长这些相关量之间的关系都推导一遍那这题就刷得很值了。我个人刷完这题的感觉是看答案一分钟理解证明才是真正的收获。把“为什么相遇”从直觉上升到数学结论之后再遇到类似的追及类问题就会有一种通了的感觉。希望你也能体会到这种从“看懂代码”到“真正掌握”的转变。
说实话刷到 Hot100 第 22 题的时候我心里是有点轻视的——环形链表这题名听着太基础了第一反应就是“哈希表嘛遍历一遍记个地址就行”。但后来在一次模拟面试里被面试官追问了一句“不用额外空间怎么做”我当场愣住才意识到这题藏着一个特别经典的快慢指针思想也就是 Floyd 判圈算法。后来我把两种解法、边界条件、证明过程甚至扩展题 142 都完整啃了一遍才发现这题虽然标着 Easy考点密度却一点都不低。这篇就把我完整的做题过程和思考整理出来包含完整代码、复杂度分析、面试现场怎么讲、以及大概率会被追问的找环入口推导。无论你是刚入门算法题的新手还是准备跳槽面试需要快速过 Hot100 的老手这篇应该都能给你省不少时间。1. 题目卡点和核心思路拆解1.1 题目到底在考什么题目本身就一句话给定一个链表的头节点 head判断链表中是否有环。如果有环返回 true没有环返回 false。很多人第一眼觉得这题简单但它真正考的东西其实很具体链表节点的存储特点和指针追及问题的数学直觉。链表在内存里是一串节点每个节点有一个 next 指针指向下一个节点地址。如果链表中存在环就意味着某个节点的 next 指针指向了之前已经出现过的某个节点从那里开始遍历会永远循环下去形成一个封闭的环。这里有个容易踩的坑环的存在跟节点值完全无关判断条件必须基于节点的引用内存地址而不是节点上存的值。两个不同节点可以有相同的 val这时如果用值去判重就会得到错误结果。LeetCode 上给的链表节点结构大概是这样class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } }题目要求返回布尔值但实际面试时面试官往往不会停留在“会不会做”这个层面而是会追问“为什么快慢指针一定相遇”“空间复杂度能不能做到 O(1)”“能不能找环的入口”。这题就像一个入口背后牵扯出一整套链表问题的解题框架。1.2 先说结论两种解法一个玩空间一个玩时间这题的标准解法就两个方向理解它们的差异比背代码重要得多哈希表法遍历链表每经过一个节点就把它的引用存进一个 Set如果遇到某个节点已经在 Set 里说明存在环。时间复杂度是 O(n)空间复杂度也是 O(n)。快慢指针法维护两个指针slow 每次走一步fast 每次走两步。如果链表没有环fast 会先到达末尾如果有环fast 和 slow 一定会在环内某一处相遇。时间复杂度 O(n)空间复杂度 O(1)。两种方法的取舍很清楚哈希表法直观、代码简单、不容易出错快慢指针法空间更优而且是面试官更想听到的解法。大部分 LeetCode 官方题解以及各大厂面试的标准答案都会默认你会快慢指针。所以哈希表应该是你脑中第一个跳出来的思路但快慢指针才是你真正要写进简历的解法。1.3 一个重要的前置心智模型在写代码之前我建议你先建立一个心智模型链表不是一条“线”而是一串内存地址的链式结构。当你遍历链表时指针是在“节点地址”之间移动而不是在“值”之间移动。这个模型有助于你理解为什么哈希表存的是节点引用以及为什么快慢指针的相遇判断可以精确到地址相同。从这个角度去看环形链表本质上是一个“指针是否会回到已访问地址”的问题。哈希表法用额外的空间记录“已访问地址”快慢指针法则利用“不同速度在封闭环内必然追及”的数学性质省掉了记录空间。后面的所有代码都是围绕这两个视角展开的。2. 解法一哈希表最简单也最容易想到2.1 哈希表解法原理哈希表法的思路非常符合直觉。你可以想象成走迷宫的时候每到一个路口就把门牌号记在本子上。如果走着走着发现当前门牌号在本子上已经出现过那就说明你绕回到了已经走过的位置前面是一个死循环。具体到链表就是初始化一个空的哈希集合从 head 开始遍历每到一个节点就检查这个节点的引用是否已经在集合里。如果在直接返回 true如果不在就把节点引用加进集合然后继续走。如果遍历到 null说明链表走完了也没遇到重复节点返回 false。这里我再强调一次集合里存的是节点对象本身的引用。Java 的 HashSet 会调用对象的 hashCode 和 equals 方法而 ListNode 默认的 hashCode 是基于内存地址的所以存引用天然能区分不同节点。如果你自作聪明去存 val一旦链表里有重复值结果就是错的。2.2 Java 代码实现带注释走读public boolean hasCycle(ListNode head) { // 记录已经访问过的节点引用 SetListNode seen new HashSet(); ListNode p head; while (p ! null) { // 如果当前节点之前出现过说明存在环 if (seen.contains(p)) { return true; } seen.add(p); p p.next; } // 遍历到链表终点说明没有环 return false; }这段代码逻辑非常直白唯一的注意点是SetListNode的泛型类型必须是 ListNode而不是 Integer。只要节点是同一个对象哈希集合就能识别出来。2.3 复杂度与隐藏的问题哈希表法的复杂度分析很简单时间复杂度O(n)最坏情况下需要遍历所有节点才得出结果。空间复杂度O(n)最坏情况下所有节点都被放进集合占用与节点数成正比的内存。表面上看起来这个解法“稳”但问题也就出在空间上。当链表长度达到几万甚至几十万节点时额外开一个 HashSet 的内存开销并不小。而且在算法面试里凡是题目考查“链表 环”这个组合面试官基本都会要求你给出 O(1) 空间的方案。如果一上来就只会哈希表很容易被判定为“思路比较基础”。2.4 什么时候该放弃哈希表优先考虑双指针我的建议是如果面试官没有提任何限制条件哈希表法是很好的第一回答因为它最直观能体现你能够快速给出一个正确解法。但当面试官追问“能不能优化空间复杂度”时你就要立刻意识到他期待的答案是快慢指针。这时候就不要再去纠结哈希表的常数优化了直接转向快慢指针才是正路。还有一种情况也该优先用快慢指针当链表长度很大、内存紧张或者你在嵌入式、底层系统中处理链表O(n) 的空间开销可能是不可接受的。工程上的链表通常不会无限长但面试考察的本质是你在资源受限时的取舍能力。所以快慢指针不是“炫技”而是真正有工程意义的解法。3. 解法二快慢指针真正该学的解法3.1 Floyd 判圈算法是怎么想到的快慢指针有一个正式的名字Floyd 判圈算法Floyds Cycle Detection。它的思想来源特别生活化在一个环形跑道上如果两个人同时出发一个人跑得快、一个人跑得慢那么跑得快的人最终会从后面追上跑得慢的人。在一条笔直跑道上跑得快的人只会先到终点永远不会被追上。把链表类比成跑道唯一的问题是快指针必须每次比慢指针多走一步也就是 fast 每次走两步、slow 每次走一步。这样才能保证两者在环内相对速度是 1从而在数学上一定能追上。如果你让 fast 走三步、四步虽然有时候也能相遇但这个“有时候”就是最大的风险后面第 5 节我会专门讲这个问题。3.2 证明为什么两步一追就一定能碰面这里需要一点简单的数学证明面试的时候能讲出来是加分的。为了方便理解我把证明拆成两步第一步如果链表没有环fast 每次走两步它会比 slow 更快到达 null。所以 while 循环会在 fast 或者 fast.next 为 null 时终止返回 false。这很好理解。第二步如果链表有环slow 进入环之后fast 一定已经在环里了因为 fast 跑得快可能已经绕了好几圈。此时把环看成一条环形跑道fast 在 slow 的“前方或者后方某个位置”两者的相对距离记为 d。由于 fast 比 slow 每秒多走一步所以每过一个单位时间两者的距离 d 就会减少 1。当 d 减少到 0 时两者就在同一个节点上相遇。因为每次减少的是 1一个正整数总能在有限步内归零所以相遇一定发生。这个证明就是 Floyd 判圈算法的核心。面试时你只要把这个逻辑说清楚面试官基本就会认可你的理解。3.3 Java 代码实现带注释走读public boolean hasCycle(ListNode head) { // 空链表或只有一个节点不可能成环 if (head null || head.next null) { return false; } ListNode slow head; ListNode fast head; // fast 每次走两步所以要保证 fast 和 fast.next 都不为 null while (fast ! null fast.next ! null) { slow slow.next; // 慢指针走一步 fast fast.next.next; // 快指针走两步 // 地址相同说明追上了存在环 if (slow fast) { return true; } } // fast 走到链表末端无环 return false; }这段代码有几个关键点要说一下。循环条件是fast ! null fast.next ! null因为 fast 在循环体内要访问fast.next.next如果fast.next本身就是 null就会出现空指针异常。另外slow 和 fast 都初始化为 head然后先移动、后判断这个顺序也很有讲究我们第 5 节会单独讲。3.4 复杂度分析与几个小细节快慢指针的时间复杂度是 O(n)空间复杂度是 O(1)。很多资料直接写“时间复杂度 O(n)”但完整说法是链表无环时fast 遍历到末尾耗时约 n/2 步链表有环时slow 进入环后最多在环内走不到一圈就会被 fast 追上所以总步数仍然是 O(n)。这里的“最多走不到一圈”可以用一个直觉解释fast 相对于 slow 每秒缩短 1 单位距离而两者初始距离最多不超过环长 L所以追及所需时间不超过 L。面试时可以说“时间复杂度是线性的具体常数跟环的位置有关但整体不会超过 O(n)”。还有一个细节快慢指针在环内的相遇点一定在环的入口之后不会在入口之前。这一点在后续推导环入口时很关键先留个印象。4. 实操过程从读题到提交通过的完整复盘4.1 边界条件怎么处理这题虽然简单但边界条件处理不好照样会出问题我梳理了三个最容易踩的空链表head 为 null没有节点必然无环。直接返回 false不需要进入循环。只有一个节点head.next 为 null也必然无环。同样直接返回 false。单节点自环head.next 指向自身这种情况下链表只有一个节点但它确实是一个环。此时快慢指针都从 head 出发slow 走一步还是回到 headfast 走两步也会回到 head两者在第二轮相遇返回 true。前两个边界条件我习惯在函数开头统一处理if (head null || head.next null) { return false; }这样写既简洁又能避免后面的空指针问题。单节点自环的情况则不需要特殊处理快慢指针代码本身就覆盖了。4.2 完整测试用例设计写算法题不能只满足于“过了 LeetCode 的样例”我一般会在本地或者脑子里过一套完整的测试用例确保边界覆盖到位。下面这个表是我自己常用的测试矩阵用例链表结构预期结果空链表head nullfalse单节点无环1 - nullfalse单节点自环1 - 自身true两个节点无环1 - 2 - nullfalse两个节点成环1 - 2 - 1自环true链尾指向中间1 - 2 - 3 - 4 - 2true链尾指向头节点1 - 2 - 3 - 1true长链表无环1 - 2 - ... - 10000 - nullfalse这套用例基本覆盖了所有分支空、单节点、多节点、环在头部、环在中间、自环、无环。写题时把这些情况在脑子里过一遍代码的健壮性会明显提高。4.3 Python 实现有什么不同国内不少读者用 Python 刷题Python 版本和 Java 的差别非常小重点在于判断引用相等时要用is而不是。在 Python 中可能会触发对象内容的比较而我们要的是地址判断所以必须用is。顺便给一个可以运行的版本def hasCycle(self, head: ListNode) - bool: if not head or not head.next: return False slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False这段代码在 LeetCode 上可以直接跑通。Python 的代码虽然简洁但面试手写时要注意类型标注不一定要写全重点是把逻辑讲清楚。我个人一般先写 Java 版本因为 Java 对空指针的约束更严格写的时候会下意识想清楚每一个next是否可能为 null反而更容易避免边界错误。4.4 面试现场如何一步步说清楚面试的时候建议按照下面这个顺序由浅入深地表达效果最好先说暴力解“首先我可以遍历链表把访问过的节点放进 HashSet如果遇到重复节点就有环。这样做时间 O(n)、空间 O(n)。”主动提出优化“题目如果要求空间 O(1)我可以用快慢指针慢指针走一步快指针走两步。如果没有环快的会先遇到 null如果有环两者最终在环内相遇。”补充正确性证明“因为快指针相对慢指针的速率为 1 步/单位时间每次追 1 个单位的距离所以有限步内必然追上。”提边界“空链表、单节点链表直接返回 false单节点自环的时候两个指针走完一轮会相遇。”写代码然后自己过一遍测试用例。这套表达方式的妙处在于不管面试官接下来追问什么你都已经把思路、证明、边界全部展示过了后续对话基本就在你的节奏里。我第一次模拟面试时只说了代码没有讲证明结果被追问“你怎么证明一定相遇”时卡住了。后来我把证明补上整个回答的完成度完全不一样。5. 常见问题与避坑踩过才懂的点5.1 快指针走三步行不行我劝你老实走两步这是我在学习过程中产生过的最大的疑问既然 fast 走两步能追上为什么不能走三步、四步这样不是更快吗实际测试下来走三步在部分情况下确实能相遇但无法保证在所有环形链表上都相遇。背后是数学上的同余问题。设环的长度为 L快指针每单位时间走 k 步慢指针走 1 步速度差 d k - 1。假设某一时刻两者的相对距离为 r那么二者相遇的数学条件是存在整数 t 使得 r d·t 能被 L 整除。这个同余方程等价于 d·t ≡ -r (mod L)有解的充要条件是 gcd(d, L) 能整除 r。标准解法中 d 1任何 r 都能被 1 整除所以一定相遇。而如果你让 fast 走三步d 2如果环长 L 是 4初始相对距离 r 是奇数gcd(2, 4) 2 无法整除 r则永远不可能相遇。所以面试时千万不要自作聪明写 fast fast.next.next.next。标准答案就是两步一步因为只有这个速度差能保证判断绝对正确。5.2 死循环和空指针是怎么出现的快慢指针写法有一个常见的隐藏 BUG先判断等于 head再移动。假设你把判断写成while (fast ! null fast.next ! null) { if (slow fast) { return true; } slow slow.next; fast fast.next.next; } return false;这个写法在普通无环链表上没问题但在单节点自环时初始 slow 和 fast 都等于 headwhile 循环一进去就直接命中slow fast返回 true结果某种程度上依然正确。真正的问题出在有环但入口不在 head 的链表上——初始判断的时候 slow 和 fast 都在 head这个判断并没有做错但会误导你忽略一个事实判断相遇应该放在移动之后。因为初始时两个指针本来就在同一个起点这个“相遇”毫无意义。更经典的错误是循环体内先判断fast.next.next而忘记检查fast.next是否为 null。如果链表长度是奇数fast 走到最后一个节点时fast.next为 null此时再去取fast.next.next就会抛 NullPointerException。所以必须把fast ! null fast.next ! null同时写在 while 条件里。5.3 哈希表法的隐性限制哈希表法也有一个容易忽略的点两个不同节点可能拥有相同的值所以集合里必须存节点引用。如果你误存了ListNode.val当链表中有两个值为 3 的不同节点时第二个就会被误判为“已经出现过”从而把无环链表判成有环。另外Java 的HashSetListNode是因为 ListNode 默认equals才达到正确语义的。如果你在真实工程里自定义了一个重写了 equals 的链表节点类用哈希表判环前就要想清楚这个 equals 是基于值还是引用。基于值的 equals 在这个场景下会让哈希表法失效。这也是我为什么强调“理解哈希表存的是引用”比记住代码更重要的原因。6. 进阶这题背后还能挖出什么6.1 变体题找环入口142 题原理推导Hot100 里紧接着就有一道关于环形链表的变体题142. 环形链表 II要求返回链表中环开始的节点。很多同学背下了代码但不理解为什么相遇后把一个指针放回头节点再同步走一次就能找到入口。这里我把推导写清楚建议收藏。设链表中 head 到环入口的距离为 a环入口到快慢指针相遇点的距离为 b相遇点到环入口的距离为 c环长为 L b c。慢指针从 head 到相遇点一共走了 a b 步。快指针速度是慢指针的 2 倍所以它走的距离是 2(a b)。同时快指针走的路程也可以写成a b kL其中 k 表示快指针在相遇前绕了 k 圈。于是有2(a b) a b kL进一步化简a b kL再代入 L b ca kL - b (k - 1)L c这个式子的含义是从 head 走到环入口的距离 a等于从相遇点继续走 c 步绕了 k-1 圈之后的距离。因此推导出解法第一次相遇后把一个指针放回 head另一个留在相遇点两者都以步长 1 移动再次相遇时的节点就是环入口。这个推导我建议你亲自在草稿纸上画一遍图半个月后都不会忘。面试现场能当场推导出来的候选人通常都能给面试官留下很好的印象。6.2 工程场景里的环形链表你可能觉得链表判环只是个面试题实际工程中用得不多。其实环形结构在系统设计里非常常见CPU 调度里的循环队列、网络数据包的环形缓冲区、某些缓存淘汰算法里的循环链表都是“链表 环”的形态。当这些结构出现异常比如某个 next 指针被错误地指回之前的位置就会导致死循环、CPU 占用飙升、服务卡死。我在定位线上问题时确实遇到过一次类似的现象某个消息队列消费者线程一直不退出日志刷个不停最终定位下来是队列的某个节点被错误改写了 next 指针形成了一个意外的环。那时候我才真切感受到判环不只是一个算法题它也是一种排查无限循环问题的通用思路。就算链表不大指针故障引发的服务异常也可能很严重掌握这个工具相当于给自己储备了一个应对循环问题的检测手段。另外不断轮询的 DNS 负载均衡、循环链表实现的进程调度等场景天然就需要能正确识别“这个环是我想要的还是异常产生的”。所以把快慢指针吃透对后面的系统设计面试也有帮助。6.3 一个刷题方法论的建议最后分享一个我自己刷题的方法凡是链表题一律先在纸上画图标出每个指针的位置变化再写代码。尤其是环形链表这种需要“动态追及”的题目光靠脑子想很容易漏边界画图之后每一步都很清楚。具体做法是画一条链表把 slow 和 fast 的当前位置用两个不同颜色的点标出来然后逐步推进模拟 3 到 5 步。你会直观地看到 fast 进入环、slow 后进入环、两者距离逐步缩短直到相遇的完整过程。这个习惯帮我解决的不只是 141 和 142还包括后面一大堆链表操作题比如反转链表、合并有序链表、删除倒数第 N 个节点。链表题本来就依赖空间想象多画图不会亏。第二点建议是不要只满足于“提交通过”。LeetCode 上通过这一题很容易代码也不长内核是快慢指针的理解和 142 的推导。这两个点才是这题真正的价值所在。如果你能顺手把相遇点、环入口、环长这些相关量之间的关系都推导一遍那这题就刷得很值了。我个人刷完这题的感觉是看答案一分钟理解证明才是真正的收获。把“为什么相遇”从直觉上升到数学结论之后再遇到类似的追及类问题就会有一种通了的感觉。希望你也能体会到这种从“看懂代码”到“真正掌握”的转变。
