刷题这件事最怕的不是不会做而是做了就忘、错了就改、改了再错最后只在提交记录里留下一个“Accepted”。Linked List Cycle Detection这道题在 LeetCode 上标着 easy链表、环检测、双指针听起来都是再基础不过的概念但我在不同阶段反复做它每次都能踩到不同的坑指针指错、边界漏判、异常情况没考虑、退出条件不对。这类“简单题”恰恰是最能暴露基本功的地方。今天用这道 Linked List Cycle Detection 当例子把我自己栽过的跟头、调试的过程、以及事后整理的思路完整过一遍希望能帮刚开始刷题的朋友避开同样的弯路。这道题要解决的问题很简单给定一个链表判断链表中是否存在环。题目输入的是链表头节点 head如果链表里某个节点的 next 指针重新指向了链表中某个先前节点就说明存在环。代码层面常见做法有两种哈希集合HashSet和快慢指针Floyds Cycle Detection也叫龟兔赛跑算法。但真正把两种做法写到 bug free需要考虑的细节远比题目定义的“easy”要多。1. 题目拆解链表中环到底是什么1.1 环的结构与原题要求链表中的环不是一种独立的数据结构而是指某个节点的 next 指针没有指向空地址 null而是指向了链表中已经出现过的某个节点导致从该节点出发可以无限遍历永远无法到达链表尾部。题目会给出节点定义class ListNode { int val; ListNode next; ListNode(int x) { val x; next null; } }判断是否存在环返回值是布尔值 true 或 false。LeetCode 上这道题的输入参数是 head但在实际面试中面试官往往还会追问能否不用额外空间能否给出入口节点能否证明算法的正确性这就是为什么基础题也值得反复打磨。第一阶段我给自己定的要求是写出功能正确的代码第二阶段要求是能够解释清楚每个变量在做什么第三阶段要求是能口头推导证明和举反例。这道题我经历了完整的三阶段。1.2 环的本质next 指针的非法回跳从指针结构来看无环链表中必然存在一个节点的 next 为 null这也是遍历终止的唯一充分必要条件。有环链表中不存在任何 next 为 null 的节点所以任何依赖“遍历到 null 结束”的算法都会陷入死循环。判断环的存在本质上就是判断“这个链表有没有终点”。理解这一层后很多错误就变得清晰了比如有人写 while (head ! null) 后更新 head head.next对于有环链表head 永远不为 null程序永远不会结束提交后表现为超时 Time Limit Exceeded。这不是题目难而是没有意识到“无终点的链表不能靠终点来判断”。再进一步环可能出现在链表任意位置不一定从首节点开始。比如 1 - 2 - 3 - 4 - 2环的入口是 21 - 2 - 3 - 1环从首节点就开始了。测试用例一定会覆盖头部成环和尾部成环两种情况。我最初写测试时只验证了尾节点指向中间节点的情况漏掉了 head 自己指向自己的场景导致哈希集合解法里判断条件写错也没发现。1.3 为什么说这是一道“披着 easy 外衣”的链表入门题Linked List Cycle Detection 本身解法不长代码量在 10 到 20 行之间但涉及的知识点密度很大链表遍历、指针更新、哈希表使用、数学上的追及问题、异常输入处理。很多 easy 题考的是“固定套路背诵”这道题考的是“对遍历本质的理解”。它还是后续一系列题目的基础包括寻找环入口、寻找两个链表的交点、寻找链表中点、判断回文链表几乎都用到快慢指针思想。因此把它真正吃透比盲目刷五道同难度新题更有价值。2. 解法一哈希集合最直观但最容易在细节上翻车2.1 基本思路与参考实现用一个 HashSet 保存已经访问过的节点遍历链表每次判断当前节点是否已经在集合中。如果某个节点重复出现说明形成了环如果遍历到了 null说明无环。最直接的代码长这样public boolean hasCycle(ListNode head) { SetListNode seen new HashSet(); ListNode cur head; while (cur ! null) { if (seen.contains(cur)) { return true; } seen.add(cur); cur cur.next; } return false; }这里保存的是节点对象的引用不是节点的值因为环的定义是“同一个节点被再次访问”而不是“值相同”。如果两个不同节点的 val 相同但它们是不同对象不算成环。这是哈希集合解法里最核心的一个判断很多新手写成了 seen.contains(cur.val)一旦链表里存在重复数值就会在没有环的情况下错误地返回 true。我初次刷题时就犯过这个错当时测试用例刚好有一个 1 - 1 - 2 的链表我第一次迭代遇到第二个值为 1 的不同节点集合里已经有值 1代码直接返回 true白白提交一次错误答案。2.2 参数设计的关键过滤是否有环后再判断出口哈希集合解法的时间复杂度是 O(n)空间复杂度是 O(n)因为最坏情况下要把所有节点存进集合。它虽然不如快慢指针优雅但胜在思路直观适合作为思考的第一步。写这个解法时常见的错误除了“用值代替引用”还有“忘记在遍历前保留头节点”和“遍历过程中修改了 head”。有的朋友喜欢直接用 head 遍历return 之后发现 head 已经变了虽然不影响本题返回布尔值但如果题目后续要求返回入口节点就必须提前保存头节点。我的习惯是单独定义 cur 变量head 始终作为链表的“根引用”保留。2.3 哈希解法的边界条件与思考方式边界条件包括 head 为 null、head.next 为 null。这两种情况不可能有环因为环至少需要两个节点自己指向自己也需要节点内 next 非空。当采用 while (cur ! null) 循环时这两种情况会自然退出不需要单独写 if 判断。但如果采用 do-while 结构就必须在进入循环前判断 head 是否为空否则会空指针异常。我最初从“判断节点集合”的角度理解没有意识到不同循环结构的区别在改写代码时踩过坑。另外哈希集合解法里“先判断再添加还是先添加再判断”顺序不同结果一样但会影响你如何理解“重复”的含义。先判断后添加遇到环的入口节点时就会检测到重复先添加后判断则进入入口节点时集合中并不包含该节点要等到 cur.next 指回它、下一轮循环才会检测到此时判断的是同一个节点第二次出现。这两种写法都能正确工作但在提交后正确写法会少一次迭代。对于性能要求不高的 easy 题这不算什么问题但能反映做题人思考的严谨度。3. 解法二快慢指针最优解背后的物理直觉3.1 快慢指针为什么能检测环快慢指针的思路来自“龟兔赛跑”在环形跑道上速度不同的两个运动员最终一定会相遇。链表中有环时慢指针每次移动一步快指针每次移动两步两者都进入环后因为速度差为 1每轮快指针相对慢指针靠近一步最终会追上。无环时快指针会先到达 null循环就可以终止。核心代码非常短public boolean hasCycle(ListNode head) { if (head null || head.next null) { return false; } ListNode slow head; ListNode fast head.next; while (slow ! fast) { if (fast null || fast.next null) { return false; } slow slow.next; fast fast.next.next; } return true; }这段代码是 LeetCode 官方给的版本也是最容易 bug 的版本之一因为它的初始化和循环条件不直观。有的版本会让 slow 和 fast 都从 head 开始循环条件写成 while (fast ! null fast.next ! null)这也行但需要注意它们一开始就相等while 循环可能不会进入导致处理逻辑不同。两种风格的差异恰恰是做题时最容易混淆的地方。3.2 步长与初始化选择的错误案例我见过很多自行实现的版本把 fast 初始化为 headslow 初始化为 head.next结果出现两种情况一是空链表时直接空指针二是两个指针一快一慢反向移动永远无法相遇。还有人把快指针步长写成了 fast fast.next即两个指针同速走那就退化成了普通遍历只有链表恰好是环且头尾相接时才可能“相遇”完全失去了检测环的能力。写错步长不会立即报错只会得到错误答案这种隐藏 bug 最让人头疼。初始化方式上我个人的建议是统一采用“slow head, fast head”的形式循环条件控制好快指针的合法性public 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; }这种写法的好处是逻辑顺序清晰先判断快指针能否走两步能走再移动移动后比较。它彻底避免了对 head.next 的判空依赖。前面提到的官方解法需要先判断 head null || head.next null因为 fast 初始化为 head.next如果链表只有一个节点fast 就为空后面判断就无从谈起。两种写法都能过但我用后一种时脑子更清楚面试讲起来也更顺。3.3 为什么不会错过环追及问题的数学证明面试中经常被问为什么快指针一定能追上慢指针而不是反复擦肩而过这里的关键是它们在一个“环”里同向移动快指针相对慢指针的速度是 1 步/轮。假设环的长度为 L从某个时刻开始慢指针在环中位置为 a快指针位置为 b两个位置都按从入口算起的偏移量表示两者距离记作 d (b - a) mod L。每一轮移动后距离缩小 1所以最多 L 轮后距离会变为 0也就是两者相遇。更重要的是在慢指针进入环之前快指针可能已经在环里绕了很多圈但只要慢指针进入环两者距离就是一个有限值最终必然相遇。这个证明我最初完全说不清楚后来自己拿一张纸画了几条不同长度的环长度 3、4、5把移动过程一步步列出来才真正明白“距离差收敛”不是靠运气而是确定性过程。从链表全局来看无环情况下快指针会先到达 null循环自然退出。有环情况下快指针永远不会遇到 null因此循环一定会以“两个指针相等”为出口返回 true。两个出口互斥且完备所以算法是正确的。4. 边界条件与测试用例设计一道 easy 题的隐藏考点4.1 必须覆盖的六类测试数据我梳理了常见测试列表不建议只依赖题目自带的例子而是自己手写构造方式来验证场景链表结构期望结果验证重点空链表nullfalse指针是否空操作单节点无环1 - nullfalse快慢指针初始是否安全单节点成环1 - 自指true能否检测到首节点环两节点成环1 - 2 - 1true入口在头部两节点无环1 - 2 - nullfalse正常遍历结束环形在链表中部1 - 2 - 3 - 4 - 2true入口不在头部超长链表10^5连续无环false是否会超时或栈溢出这里尤其要注意单节点成环的构造方式在 Java 里可以写ListNode node new ListNode(1); node.next node;。很多刷题者在本地测试时只会构造无环的单节点没有主动构造自环场景导致哈希集合解法中“先判断后添加”和“先添加后判断”两种写法的差异没有被察觉。我建议每次拿到链表题先写一个本地工具类来构造节点再写几个静态方法生成有环/无环样例这样跑起来比反复提交 LeetCode 快得多。4.2 构造测试链表的本地代码片段如果想快速实验可以用下面的 JavaScript 或 Java 代码手动构造。JavaScript 版本可以用对象模拟节点function ListNode(val) { this.val val; this.next null; } function buildList(arr, pos) { const nodes arr.map(v new ListNode(v)); for (let i 0; i nodes.length - 1; i) { nodes[i].next nodes[i 1]; } if (pos 0) { nodes[nodes.length - 1].next nodes[pos]; } return nodes[0]; }比如 buildList([1, 2, 3, 4], 1) 就构造出 1 - 2 - 3 - 4 - 2正好是一个环入口在第二个节点的链表。用这样的工具函数可以在本地一次性把多个场景跑完还能用 console.log 或 debugger 观察指针移动轨迹。第一次手动构造时我还发现数组下标一定要对应好如果 pos 超过了数组长度会得到 undefined反而制造出一个无环链表容易误判测试结果。4.3 边界条件为什么是 easy 题的致命伤对于 easy 题很多人觉得“我能写核心逻辑就够了”但面试官考察的恰恰是代码在极端输入下是否健壮。头节点为 null 是最简单的边界但如果解法里用了fast.next.next空链表会在第一步就抛 NullPointerException如果判断顺序写成while (fast.next ! null fast ! null)当 fast 为 null 时去访问 fast.next 也会抛异常。这种“判空顺序错误”我犯过不止一次。正确做法是永远先校验当前节点本身不为空再访问它的 next顺序不能反。Java 和 Python 里都有短路求值先写fast ! null再写fast.next ! null是安全的反过来就会出事。另一个容易忽略的边界是“一个节点next 指向自己”。快慢指针从同一个节点出发循环条件 while (fast ! null fast.next ! null) 成立因为 fast.next 指向自身非空。移动一步后 slow 仍在节点 1fast 再移动两步也仍在节点 1比较相等返回 true。这个过程很完美但如果你用官方版本的while (slow ! fast)初始化时 slowhead、fasthead.next而 head.next 正好是 head那么 slow 和 fast 一开始就指向同一个节点循环根本不会执行直接返回 true也能得到正确结果。可见不同写法在特殊用例下行为差异很大测试用例设计得越多样越能暴露问题。5. 我实际踩过的坑五个高频错误复盘5.1 空指针异常访问了 null 节点的 next 属性这是链表题里最经典的问题。LeetCode 上提交报错一般会显示java.lang.NullPointerException同时指出错误出现在哪一行。比如写成 while (fast ! null fast.next ! null) 是安全的如果写反成 while (fast.next ! null fast ! null)当 fast 为 null 时先执行 fast.next 访问直接炸掉。解决方法是形成肌肉记忆链表节点判空永远先判自己再判 next。我在刷完十几道链表题后已经把这条规则内化成条件反射根治了大部分异常。5.2 死循环与超时快指针永远没有前进有一次我写快慢指针时快指针更新误写成了 fast fast.next慢指针也是 slow slow.next。结果无环链表上快指针比慢指针先到 null虽然能正常退出返回 false但在有环链表上两个指针同速绕圈fast 永远不会追上 slow循环无法退出最终超时。排查这类问题不能靠眼睛干瞪最好的办法是在移动指针前后打印指针的值或者画出几轮指针位置表。我用的临时 debug 代码长这样while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; System.out.println(slow: slow.val , fast: fast.val); if (slow fast) return true; }通过打印不难发现 fast 始终落后固定的距离而不是逐步逼近。看到这个现象我就立刻意识到步长写错了。5.3 返回值错误把“有环”和“节点重复”混为一谈我在写哈希集合解法时曾经用 seen.contains(cur.next) 判断下一个节点是否出现过。这在小环上没问题但如果环的入口不是 cur.next 而是更后面的节点这种提前一步判断会漏掉情况。还有一种常见错误在向集合添加节点时错误地添加了 cur.next漏存了当前节点导致环入口无法被识别。说到底哈希集合解法的正确性建立在一个简单的循环不变量上Set 中保存的是所有已经遍历过的节点。任何破坏这个不变量的写法都会出错。所以我在复盘时特别强调“每一步操作后集合的内容是什么”想清楚再写代码。5.4 误判快慢指针相遇条件比较的是 val 还是节点引用有些初学朋友会用 slow.val fast.val 判断相遇这在链表节点值不多时也许碰巧能过但一旦出现环内有两个值相同的节点就会把无环链表判成有环或有环链表判成无环。环检测关注的是对象身份不是节点的值。同一道题里哈希集合法要避免用值存集合快慢指针法要避免用值判断相等这是两类高频错误。面试时如果面试官问“你比较对象还是值”就是在挖这个坑。5.5 无环链表返回 true判断时机写在了指针更新之前我尝试过把 if (slow fast) return true; 写在 slow 和 fast 更新之前导致两个初始相等的指针瞬间触发“相遇”无环链表也返回 true。这提醒我同一轮循环中必须先移动指针再判断是否相遇。如果一开始就把 slow 和 fast 指向同一个节点却期待它们在还没有移动时就算“相遇”逻辑上就乱了。当然如果采用官方版本的 while (slow ! fast)那么初始化时不能相等两者不同步移动如果采用“先移动后比较”风格则初始化相等是允许的。关键在于理解和把握自己采用的那一种循环不变式。5.6 排查问题的方法论二分定位、打印状态、构造最小用例遇到程序行为不符合预期我的排查顺序是先确认测试用例构造是否正确再确认算法步骤是否完整最后逐行对比代码。如果错误发生在 LeetCode 提交而不是本地就先简化代码到最小可执行版本在本地调试。链表题特别适合“画图法”把每个节点的 next 关系画出来同时并列画出 slow 和 fast 每一步的位置。有一次我为了解决一个边界问题手动画了一个 7 节点、环入口在第 4 个节点的链表推演了 10 轮终于看清楚快指针在慢指针进入环前已经绕了 2 圈。这种推演虽然费时间但比反复提交瞎试高效得多。6. 面试场景中的呈现方式与后续扩展6.1 如何从“答对”升级到“讲懂”代码正确只是第一步面试中聊到 Linked List Cycle Detection通常要求候选人讲清楚两件事为什么哈希集合能做为什么快慢指针省空间且一定能相遇。我建议按“暴力思路 - 优化思路 - 证明 - 复杂度”四步来讲。先说自己最直观的想法是保存访问过的节点时间复杂度 O(n)、空间 O(n)然后说能不能把空间降到 O(1)想到快慢指针接着解释为什么快慢指针不会错过可以用“两个人绕圈跑速度快的人最终一定会追上速度慢的人”来解释最后补充快指针步长为 2 的原因——只要步长差大于 0就一定能相遇步长为 2 是代码上最稳妥的写法。如果步长差为 0永远追不上如果步长太大比如差为 3依然能追上但实现时快指针需要连续跳多步判空更繁琐没有明显优势。6.2 进一步追问如何找环的入口这道题的 follow-up 一般不是让你进一步优化已经 O(1) 空间了而是让你返回环的起始节点即 142. Linked List Cycle II。思路是用快慢指针找到相遇点后把一个指针放回头节点另一个保持在相遇点然后两个指针都一次走一步再次相遇的节点就是环入口。这个结论并不直观需要数学推导。我自己推导过一遍设头节点到环入口的距离为 a入口到第一次相遇点的距离为 b环的剩余长度为 c那么慢指针走了 ab快指针走了 ab n*(bc)因为快指针速度是慢指针的 2 倍所以 2(ab) ab n*(bc)可以推出 a (n-1)*(bc) c也就是说从头节点出发走 a 步与从相遇点出发走 c 步二者在环入口相遇。理解了这个推导面试时就能做到有理有据。6.3 同类题串联快慢指针能力的应用地图这道 easy 题的价值还在于它能延伸到一系列 medium 题目寻找链表中间节点慢指针走一步、快指针走两步快指针到末尾时慢指针所指就是中间节点。寻找链表倒数第 k 个节点快指针先走 k 步然后两个指针同步推进快指针到 null 时慢指针的位置就是倒数第 k 个节点。判断回文链表先用快慢指针找到中点再反转后半段最后逐个比较。寻找两个链表交点可以先计算长度差或采用双指针同步交换的方式。因为它们共享“双指针控制速度”的思想我建议按“环检测 - 环入口 - 中点 - 回文”的顺序刷每道题都刻意问自己一次当前这个场景为什么快指针要走两步为什么有时又要恢复同步速度这种追问比单纯记录题号有用得多。7. 从错误中学习的整理方法让错题真正发挥作用7.1 建立“错因”分类而不是“错题”收集很多人整理了错题本但只是把题目和答案贴进去过了一个月再翻除了能记住答案错因完全想不起来。我的做法是给错题打标签比如“空指针”“边界没考虑”“步长错误”“误用 equals 比较对象”然后每个月统计一次标签频率。拿 Linked List Cycle Detection 来说我最初的错误标签是“边界没考虑”后来扩展出“指针更新顺序错误”和“比较对象还是值”。每个标签对应一条具体的检查清单下一次遇到链表题先把清单扫一遍很多错误能直接在编码过程中规避。7.2 四步复盘法重现、最小化、修正、举一反三每次提交错误后我不急着点开别人的题解而是先做四步第一步在本地用样例重现错误第二步把导致错误的输入简化成最小用例第三步用最朴素的输出观察程序状态定位到底是哪一步违反预期第四步修正代码后再想一遍这个错误还可能以什么变形出现在其他题目里。用 Linked List Cycle Detection 举例快慢指针步长写错的根本原因是“快指针必须比慢指针少走一段距离才能追上”那么同样的问题可能出现在“排序链表去重”中前驱指针忘记更新。发现不同题之间共享同一套“根本错误”复盘效率会高很多。7.3 从错误中建立“防错型编码习惯”刷题不只是在编码时找答案更是在建立一套个人的防错机制。我的防错清单里最常用的一条在链表题目中任何对 next 的访问都先问一句这个节点可能是 null 吗第二常用的一条涉及两个以上指针的题目先把指针移动规则写清楚再写循环体绝不在写代码过程中凭感觉改步长。第三常用的一条提交之前去检查头节点为空、单节点、双节点、自环、环在尾节点以及无环长链表这些固定场景而不是只依赖题目示例。这套清单就是在一次次错误中自然沉淀下来的比任何题解都适配自己的思维漏洞。刷 easy 题的目的从来不是追求“答案能跑通”而是让每一次错误都成为下一次编码时的免疫记忆。Linked List Cycle Detection 这道题我只用了两个星期从第一次提交报错到最后能完整讲出证明过程中间踩过的坑远不止上文提到的这些。现在回头看最值得庆幸的不是最后写出的代码有多简洁而是我终于养成了把 bug 拆解成“错误模式”的习惯。每当再次遇到链表指针问题时我脑子里会自动弹出那些曾经让我卡壳的瞬间然后带着更谨慎的态度下笔。希望这篇文章也能帮你把错误变成经验下次再做链表题时少一次瞎试多一分笃定。