说实话LeetCode 141这道题我在面试中问过别人也被别人问过刷题网站上的题解翻了不下二十篇。环形链表、哈希表、快慢指针这几个词几乎绑定在一起出现但真正能把为什么快慢指针是最优解讲透的人不多。多数人只是背下了快指针走两步慢指针走一步相遇就是有环至于为什么一定会相遇、能不能走三步、哈希表和数组解法各自的问题在哪其实并没有想清楚。这篇我就把这道题的三种主流思路拆开揉碎从原理到代码再到面试话术一次说清。1. 题目本质与常见误解先搞清楚环到底是什么1.1 题目定义与输入边界题目描述很简短给定一个链表的头节点head判断链表中是否有环。所谓有环指的是链表中某个节点的next指针指向了它之前出现过的某个节点导致链表在遍历时永远走不到尾。这里有几个容易忽略的输入边界空链表head为null直接返回false单节点链表只有一个节点且next为null无环单节点自环只有一个节点但next指向自己有环尾部节点指向链表中间的某个节点形成闭环。这些边界虽然简单但在笔试或面试的测试用例里都可能出现。我见过不少人在第一个if判断里只处理了head null结果遇到单节点自环的用例直接访问空指针。所以每次写链表相关的题我习惯先问自己一句每个分支下head.next是否存在1.2 核心考点不是会不会做而是能不能想明白为什么这道题在面试中的定位很典型它属于看起来简单但能聊得很深的题型。函数的返回值只是true或false但面试官真正想考察的是三件事能否快速识别出哈希表方案并说出它的时间复杂度和空间复杂度能否进一步想到不需要额外空间的方案能否解释清楚快慢指针的数学原理而不是只背结论。第3点是最关键的。因为环形链表检测不是一个孤立问题它是一个哲学层面的思想如何用有限的状态判断无限循环。快慢指针、Floyd判圈算法、龟兔赛跑本质都在解决这一类问题。理解了这一步后面做142题找环的入口、287题寻找重复数、202题快乐数都会顺很多。1.3 一个容易踩的思维误区很多初学者会把判断是否有环和判断是否有重复节点混为一谈。注意链表节点的值可能重复但节点的引用是唯一的。用哈希表判断时存储的应该是节点的引用Java中的ListNode对象、Python中的对象本身而不是节点的值。我当初就犯过这个错——用HashSetInteger存节点的val结果链表中两个不同位置的值相同就直接误判成有环了。链表节点的值重复在实际问题里非常常见所以这里必须是节点对象判重不能是值判重。2. 哈希表解法最朴素的正确解但细节决定成败2.1 思路与实现思路一句话遍历链表把每个节点存进一个哈希集合如果当前节点已经在集合中出现过说明存在环如果遍历到了null说明无环。以下是 Java 和 Python 的参考实现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; }def hasCycle(head: ListNode) - bool: seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False代码非常简单跑一遍也一定能过。但注意这里的seen存的是节点对象。如果你用set()存了cur.val只要链表里有两个节点的值相等就直接误报有环。这道题的值域没有限制所以这是必踩的坑。2.2 为什么哈希表是正确但不是最优哈希表方案的时间复杂度是O(n)空间复杂度也是O(n)。它的效率其实很高单个节点的哈希查询在平均情况下是O(1)。所以在工程代码里如果你本来就允许使用额外存储哈希表完全可以用。但它的问题在于面试官通常会追问一句能不能不用额外空间。这时候你如果只能说出哈希表面试深度就明显不够了。此外从算法竞赛的角度看O(n)的空间在数据量很大的场景下可能触及内存限制而快慢指针的O(1)空间意味着无论链表多长额外内存都是常数级别。我再来做一个直观的对比用一张表格展示方案时间复杂度空间复杂度是否改变链表工程可用性哈希表O(n)O(n)否高数组记录O(n)O(n)否中标记节点O(n)O(1)是破坏数据低快慢指针O(n)O(1)否高这里你可能已经注意到了数组记录和标记节点两种方案我把它们单独放到下一节讲因为它们确实有巧妙的切入角度也对应了题目和热搜词里的数组。2.3 哈希表的冗余优化思路哈希表的空间可以稍微压缩一点如果你知道链表的长度上限n可以使用布尔数组visited以下标表示节点地址的哈希值。但在语言层面比如 Java 中ListNode的默认哈希值是基于内存地址的直接转成数组下标并不方便。所以工程上更常见的还是用SetListNode简单直接。一个小技巧是你在while循环里可以先把cur存下来再判断也可以先判断再存。上面的写法是先判断再加入逻辑清晰。实际面试时只要表达清楚集合中的节点都是已经访问过的即可不必纠结代码顺序。3. 数组解法与破坏性标记可行但总有代价3.1 数组记录法用顺序存储代替哈希表既然哈希表可以用那么用数组/列表记录也自然可行。思路和哈希表几乎一样每访问一个节点就把它追加到数组末尾每次前进前先在数组中线性查找当前节点是否已经存在。def hasCycle(head: ListNode) - bool: arr [] cur head while cur: if cur in arr: return True arr.append(cur) cur cur.next return False这种写法的时间复杂度是O(n^2)因为cur in arr在 Python 列表里是线性查找。所以它虽然理论上正确但在性能上远不如哈希表。数组解法更值得讨论的地方在于如何让查找更快——比如用数组下标模拟哈希。3.2 基于值域假设的哈希数组如果题目给出节点值的范围比如0 Node.val 10000那么你可以用一个大小的布尔数组seen [False] * 10001每次访问节点时把seen[cur.val] True来实现 O(1) 的判重。这种做法的空间是O(range)如果值域远大于节点数就不划算如果值域小这是比哈希表更快的方式因为数组内存连续、缓存命中率高。但请你记住这种方法建立在节点值互不相同的隐含假设上。只要有重复值它就会误判。所以我在刷题时只在项目代码的特定场景下用这种值域哈希在 LeetCode 上基本不用。3.3 破坏性标记法面试中的陷阱方案关于数组的热搜词里提到数组标记我还想讲一个经常有人提出的思路修改节点结构加一个visited字段或者遍历时把节点的val改成一个特殊值比如Integer.MIN_VALUE。这样如果后续再访问到该值的节点就说明有环。public boolean hasCycle(ListNode head) { ListNode cur head; while (cur ! null) { if (cur.val Integer.MIN_VALUE) { return true; } cur.val Integer.MIN_VALUE; cur cur.next; } return false; }代码确实能跑通空间也是 O(1)但这是一种脏方案。它在遍历过程中破坏了链表中的原始数据假设有另一个线程同时读这个链表数据就直接串了。在面试场景下除非面试官明确说可以不改变数据结构否则我不建议主动提这种方法。如果提了也一定要主动说明它的副作用虽然空间是 O(1)但会修改原链表的数据实际工程中不推荐快慢指针才是无副作用的解法。这说明你有工程意识比单纯背答案加分得多。3.4 为什么不推荐把数组方案作为面试首选数组解法对比哈希表的优势几乎为零对比快慢指针在空间上又输所以它是三种解法里最尴尬的。但我在刷题初期对哈希表不熟的时候曾经就是用ArrayList硬写。它的价值在于帮助初学者理解记录已访问节点的思想但真正面试时你至少要能在哈希表和快慢指针之间自由切换。一句话总结数组解法可以练习但不能作为最终答案输出。4. 快慢指针为什么步长差一就能判定有环4.1 Floyd 判圈算法的直观原理快慢指针也叫 Floyds Cycle Detection Algorithm弗洛伊德判圈算法。设置两个指针slow和fast初始都指向head。slow每次走一步fast每次走两步。如果链表无环fast会先到达null如果有环fast一定会在环里追上slow。很多人的疑问是为什么fast一定会追上slow而不是永远差一步我通常用操场跑圈来类比。两个人在环形跑道上跑步一个速度快一个速度慢。只要跑道是环形的速度快的人一定会从后面追上速度慢的人。在这里fast比slow每次多走一步相当于每过一个单位时间fast相对slow的距离就缩短 1。设环的长度为L那么一旦两个指针都进入环内相对距离最大为L-1经过最多L-1次循环fast必然追上slow。更严谨地表述设slow进环时fast离它的距离为d0 d L每走一轮fast靠近slow一步因此最多d轮相遇。这就保证了不会出现永远差一步的巧合。4.2 完整实现代码def hasCycle(head: ListNode) - bool: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return Falsepublic 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; }注意一个细节Java 版本我写了fast head.next而不是fast head这是因为如果fast初始也等于head在无环单节点链表上slow fast会直接返回true所以要么判空要么让fast先走一步。两种写法都对但初学者往往在边界上翻车。我推荐用slow head; fast head;然后在循环前判断head和head.next是否为空这样语义更统一。另一个容易忽略的坑是while (fast ! null fast.next ! null)的顺序。在 Java 里如果写成while (fast.next ! null fast ! null)当fast为null时访问fast.next会直接抛出空指针异常。逻辑运算符有短路特性所以一定要把判空放在前面。4.3 步长为什么是 2不是 3 或更大很多人会想fast每次走 3 步、4 步是不是更快答案是不能保证相遇。由于链表是单向的指针在环内只能沿着一个方向移动。当fast每次走k步时它相对slow的收敛速度是k-1。如果k-1和环长L不互质就可能出现永远错位的情况。比如环长L3fast每次走 3 步相对速度是 2slow每走 1 步距离被拉近 2但 3 和 2 互质不环内距离的计算是模L的。当k-1与L存在公因数时fast可以沿环反复跳过slow所在的位置。选择步长 2 是最小、最简单且能保证任何环长下收敛的组合。如果你细心会发现fast走 2 步还有一个好处它一定会在有限步内到达null或进入环复杂度是 O(n)不会被无限循环卡住。而如果选更大的步长代码上判断fast.next.next...next会产生大量空指针判断写起来也麻烦。4.4 复杂度与正确性分析快慢指针的时间复杂度是 O(n)空间复杂度 O(1)。每次循环slow走一步、fast走两步相当于每轮往前走 3 个节点。无环时经过约 n/2 轮判断到空节点有环时最多经过一个链表长度加一个环长度的量级。实践中它跑得比哈希表慢一点因为要走到环内再相遇但空间优势是碾压级的。正确性的关键其实只有两点无环时fast必然先到null循环退出的条件覆盖了无环情形有环时slow和fast都进入环中且fast相对slow的步差为 1因此在有限步内必然相遇。4.5 数组、哈希与快慢指针的取舍总结如果面试官问你还有没有更好的方案你要能主动说哈希表方案空间 O(n)胜在实现简单可读性好快慢指针方案空间 O(1)是教科书级的原地判环方案且完全符合题目对空间的潜在要求数组方案一般作为思考过程提及即可不必展开。这道题的最优解没有悬念就是快慢指针。哈希表适合当你还要记录每个节点的访问顺序、做后续处理时使用如果只问是否有环快慢指针的时间与空间组合是最好的。5. 边界条件与破环点从141到延伸题的思维跳跃5.1 特殊链表的完整测试用例我整理了一份可以直接用来验证代码的边界用例建议刷完手动跑一遍用例结构预期结果空链表nullfalse单节点无环1 - nullfalse单节点自环1 - 自身true两个节点闭环1 - 2 - 1(回到1)true长链尾接中间1 - 2 - 3 - 4 - 2true长链无环1 - 2 - 3 - 4 - nullfalse我自己在本地测试时常用一个createCycle辅助函数先构造链表再让尾节点指向索引k处。写过一次之后后续很多链表题都用它来生成测试数据省了在纸上画图的时间。5.2 从141到142找环的入口才是高频进阶141 判断是否有环之后142 题要求找到环的入口节点。它的解法建立在快慢指针相遇点的基础上设链表头到环入口的距离为a环入口到相遇点的距离为b环剩余长度为c。slow走了abfast走了abk(abc)因为fast速度是slow的两倍于是可以推出a c (k-1)(bc)。这意味着如果此时让一个指针从链表头出发另一个从相遇点出发都一次走一步它们必然在环入口相遇。这个推导看起来很数学但代码和141几乎一样只在相遇后多了一段找入口的逻辑。如果141能理解142就是直接送分题。5.3 快慢指针思想在数组类问题中的应用不知道你有没有发现题目热词里出现了数组寻找重复数之类的话题。287题寻找重复数用到的是一个非常巧妙的变形把数组下标当作链表节点索引数组值当作next指针于是存在重复数就等价于链表有环。这类题做得多了会发现快慢指针不只是链表的专属工具。只要能把数据关系抽象成从一个状态跳转到下一个状态的图且每个节点出度是 1判环问题就是快慢指针的菜。数组下标跳转、函数迭代、状态机统统适用。5.4 面试加分项从一次笔试聊到工业实践在我参与的面试里能答出快慢指针的候选人不少但能主动说出哈希表适合需要记录访问历史的场景快慢指针适合纯判环场景的人少之又少。这其实就是考察你有没有在真实项目里思考过数据结构的取舍。比如说我们在做服务的分布式链路追踪时遇到过调用链配置成环导致消息死循环的问题。那本质和环形链表一模一样每个节点指向下一个处理节点其中某个节点指向了前面某个节点消息就永远无法终止。当时我们就是借鉴了快慢指针的思想在配置更新后做一次是否存在环的校验而不是等到线上循环打爆日志再去排查。这就是 LeetCode 141 的价值——它看起来只考一个链表实际上是一类有限状态检测循环的问题的通用解法。6. 刷题路线与实战建议怎样才算真正掌握这道题6.1 推荐进阶序列如果你刚做完 141我建议按这个顺序往下刷142 环形链表 II找环入口练快慢指针的推导能力287 寻找重复数数组场景的快慢指针应用感受抽象成链表的思维202 快乐数判断是否进入循环同样是快慢指针的变体876 链表的中间结点快慢指针的另一类应用快指针到终点慢指针刚好在中点。这几题做完快慢指针的三大经典考点判环、找环入口、找中点你就全覆盖了。以后再碰到检测循环的问题基本不用怕。6.2 常见错误清单我把自己刷题时踩过的坑汇总如下忘了判空while (fast ! null)里少了fast.next ! null导致空指针初始指针设置错slow和fast都从head出发但没有先排除head.next null的情况用节点值存哈希值和引用混淆重复值的用例直接误判数组解法用了val作为标记改坏原始数据后面想再遍历链表时会出错快慢指针相遇后没有做任何后续处理就直接return true这个对 141 是对的但如果你直接改 142 就容易卡住。6.3 复盘模板每道链表题都该问自己三个问题刷题不能只追求 AC。每做完一道链表题我会强迫自己回答三个问题这道题除了我用的解法还有哪些解法它们的时空复杂度分别是什么如果链表是双向的解法会变吗如果允许改变链表结构解法会变吗这个解法能抽象成什么通用模式还能用在哪些看似不相关的题目上141 的答案分别是哈希表/数组/快慢指针双向链表更容易判环可以直接查前驱标记法会变简单但会上报数据抽象出的通用模式是单步跳转图上的循环检测。刷题数量多不多其实天花板很明显。把每一道题像这样反复拷打等到面试时哪怕遇到没见过的新题也能很快把它归到熟悉的问题模型里。以上算是我刷链表专题的一部分积累。环形链表只是一个起点快慢指针这个武器拿稳了后面很多题都会轻松许多建议你亲自画一画链表图把相遇过程模拟两遍胜过背十遍代码。