第一次做 LeetCode Hot100 里的 141. 环形链表我其实没当回事想着“不就是判断链表有没有环嘛开个哈希集合记一下走过的节点不就完了”。直到面试官追了一句“能不能用 O(1) 空间做”我才意识到这道题真正的考点不是“能不能做出来”而是“能不能用快慢指针把空间复杂度打下来”。141 在 Hot100 里的地位很特殊它本身难度不高但它是链表题目里最经典的“判圈”入口后面 142、287、202 这些题全都跟同一个思路藕断丝连。这篇就围绕环形链表这道题把哈希表和快慢指针两种解法、边界条件、以及怎么从判环过渡到找入环点完整梳理一遍。适合谁看刚刷 Hot100 的新手、准备面试想理清思路的老手都适合。如果你已经 AC 过这道题也可以重点看第二部分和第四部分——快慢指针的数学原理我推导一遍边界条件和指针写法的坑我踩过不少都是文档里不会明说的东西。1. 题目到底在问什么先读懂环形链表1.1 原题描述与示例题目要求很简单给定一个链表的头节点 head判断链表中是否有环。如果链表中有某个节点的 next 指针连续指向它自己或某个更早的节点就说明存在环。返回 true 表示有环false 表示没有。力扣给的示例里有个关键约定pos 表示链表尾部的 next 指针指向的节点的索引从 0 开始但 pos 不作为参数传入只是一个帮你理解图例的标记。这个约定考试时不会给所以不要依赖它判断依据只有 head 本身。来看三个典型例子输入 head [3,2,0,-4]尾节点 -4 的 next 指向索引 1 的节点 2这就是一个长度为 4、入口在索引 1 的环输出 true。输入 head [1,2]节点 2 的 next 指向节点 1形成两个节点的环输出 true。输入 head [1]只有一个节点且 next 指向 null没有环输出 false。这三组数据基本覆盖了题目的所有形态多节点环形、双节点环形、单节点无环。我刷题时习惯先在心里模拟这三种情况再开始写代码能避免很多边界问题。1.2 这道题在 Hot100 里的位置很多人觉得 141 太简单不值得专门写一篇记录。但我的判断相反它在链表面试体系里是个“战略节点”。第一它能把链表的基本遍历从一个方向从头到尾扩展到循环结构帮你建立“链表不一定有终点”的直觉第二它引出了快慢指针这一类“双指针变体”后面 142 环形链表 II、287 寻找重复数、202 快乐数全都是同一套 Floyd 判圈思想第三它面试出现频率高很多公司会拿它当前置题你答得快、答得稳才有时间留给后面的 Hard。所以我建议把这道题当成“母题”来处理不是 AC 一遍就过而是把哈希表和快慢指针两种解法都写熟最好还能当场讲清楚为什么快慢指针能相遇。这也是我写这篇笔记的初衷——把别人只讲“怎么做”的部分补上“为什么这么做”。2. 哈希表解法最直觉的方案也是理解链表的试金石2.1 核心思路一句话遍历链表每到达一个节点就检查它是否已经出现在哈希集合里。如果出现过说明你绕了一圈回到了同一个节点这就是环如果没有出现过就把它加入集合继续往前走。走到 null 说明链表有终点那自然就没环。这个思路直白到什么程度它几乎是把“环”的数学定义翻译成了代码环就是一条路径上存在重复节点。2.2 代码实现与复杂度Python 写起来非常短class Solution: def hasCycle(self, head: Optional[ListNode]) - bool: seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False时间复杂度 O(n)每个节点最多被访问一次哈希集合的插入和查找平均 O(1)。空间复杂度 O(n)因为最坏情况下所有节点都会被存进集合。这里有一个细节cur in seen判断的是节点的引用地址不是节点的值。两个不同的节点即使 val 相同在 Python 里也是不同的对象set 也会把它们当成两个元素。这是链表的哈希解法和数组哈希解法的关键区别数组判重往往看值链表判环必须看节点本身。2.3 哈希解法的优缺点优点是正确性一目了然不容易写错几乎不需要证明缺点是空间 O(n)面试时如果水平一般把它当作保底方案是完全合理的但如果想展示自己的优势哈希并不是最优解。我自己在面试中会把哈希当作第一反应说出来紧接着补一句“这个做法空间 O(n)如果要求 O(1) 空间可以用快慢指针。”这样既展现了思维的递进也让面试官知道你懂复杂度。不过说句实话这道题如果只写哈希可能会被认为只是“背过题”——因为判断环还有一个更巧妙的办法那就是快慢指针。这也是我下一章要展开的核心。3. 快慢指针解法Floyd 判圈算法的完整推导3.1 先看代码class Solution: def hasCycle(self, head: Optional[ListNode]) - bool: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False慢指针每次走一步快指针每次走两步。如果链表有环两个指针最终一定会相遇如果没环快指针会先到达 null循环正常结束。3.2 为什么快指针走两步而不是三步、四步这是很多人忽略的问题。快指针不一定非走两步理论上走 k 步也能判环但两步有最好的工程性质。我来推导一下。假设链表无环部分是长度 L环的长度为 C慢指针入环时快指针已经领先它 d 步0 ≤ d C。从慢指针入环的那一刻开始慢指针每次走 1快指针每次走 2相对速度是 1也就是说每个单位时间快指针能追上慢指针 1 步。因为 d C所以最多经过 C 次追赶快指针必然会与慢指针相遇。这个“相对速度为 1”很重要如果快指针每次走 3 步相对速度是 2那么当 d 是奇数时可能发生“跨过”慢指针的情况——虽然多绕几圈也能碰上但在环长比较特殊的时候需要追更多圈证明更繁琐。我专门去验证过走 3 步的情况设慢指针在环内位置为 a快指针每次从位置 x 跳到 (x 3) % C那么相遇条件变成同余方程只有当 C 和 2 满足某些条件时才一定会相遇。结论是两步是保证“一定能在有限圈内相遇”的最小整数选择既快又稳还方便推导。3.3 入环前的无环段会不会影响相遇还有一点如果链表只有部分环结构比如“一条直线接一个环”快指针会在慢指针之前进入环并且在环里绕圈等慢指针。慢指针最终进入环时两者已经在环内形成了固定距离 d所以上面的推导依然成立。极端情况如果整个链表就是一个环慢指针和快指针都从 head 出发慢指针在头节点快指针第一步就到 head.next第二步就到 head.next.next。无论如何它们在一圈之内就会相遇。实际跑一遍会看到两人第一次相遇发生在环内某个位置而不是 head。3.4 复杂度分析时间复杂度 O(n)。为什么不是 O(n^2)难点在于慢指针入环后最多走 C 步就会被追上而入环前走 L 步所以总步数 L C ≤ n。快指针最多多走一个环长总步数也在 O(n)。空间复杂度 O(1)只用了两个指针这是相比哈希解法最大的优势。4. 边界条件与细节不写错循环条件的三个要点4.1 空链表和单节点最常见的边界是head is None和head.next is None。快慢指针的循环条件while fast and fast.next其实已经同时覆盖了这两种情况。空链表fast 为 None直接退出循环返回 False。单节点fast 不是 None但 fast.next 是 None同样退出返回 False。有人喜欢先写if not head or not head.next: return False这没错只是冗余。我个人的习惯是让循环条件本身去处理代码更短。但对于面试讲解写显式判断会更友好因为面试官能一眼看出你在考虑边界。4.2 先移动再判断还是先判断再移动快慢指针的代码顺序有两种写法写法 A先移动后判断相遇。while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True写法 B先判断初始位置是否相等其实相等因为都等于 head这会导致误判——如果你先判断再移动第一次循环时 slow fast 一定成立都为 head于是直接返回 True导致任何无环链表都会被判定成有环。因此一定不能在移动之前判断相等除非你先把 slow 或 fast 往前推一步。这个坑我见很多人踩过包括当年的我。4.3 快指针的 next 是否会访问空指针循环条件写成fast and fast.next是为了防止fast.next.next在 fast.next 为 None 时抛出 AttributeError。如果链表没有环快指针最终会走到最后一个节点或倒数第二个节点此时 fast.next 为 None循环退出不会访问 fast.next.next。如果链表有环快指针永远碰不到 None循环只会因为“相遇”而退出。这个保证可以用一个反证如果链表有环所有节点都在一个闭环或通向闭环的路径上任何 next 都不是 None。5. 从“有没有环”到“入环点在哪”142 题的衔接思考5.1 Floyd 判圈不只是判断如果你把 141 的解法吃透了142 环形链表 II 几乎可以顺理成章地推出来。142 要求返回入环点的节点而不是只给 true/false。Floyd 算法扩展后能做两件事先找到相遇点再重新走一遍找到入口。关键结论是这样设无环段长度为 a从入环点到相遇点距离为 b从相遇点继续走到入环点的剩余环长为 c则环长 C b c。慢指针走过的总距离是 a b快指针走过的总距离是 a b kCk 是快指针绕的圈数。因为快指针距离是慢指针的两倍2(a b) a b kC a b kC a kC - b (k-1)C c也就是说从链表头出发走 a 步和从相遇点出发走 c 步会到达同一个位置——入环点。所以代码实现是相遇后把一个指针挪回 head然后两个指针都以步长 1 前进再次相遇的位置就是入环点。我用一个具体例子验证过链表1 - 2 - 3 - 4 - 5 - 3无环长度 a2环长度 C3入环点是 3。快慢指针第一次相遇在 4此时慢指针走了 3 步1→2→3→4ab3快指针走了 6 步绕环两圈多一点。把快指针挪回 head两指针同步走走到 3 时相遇正好是入环点。5.2 把 141 的知识点迁移到其他题除了 142287 寻找重复数和 202 快乐数也是 Floyd 思想的不同变体。287 里把数组下标当成指针数组值当成 next重复数就是“入环点”202 快乐数里把 n 变换后的结果当成路径上的节点进入循环就说明不是快乐数。所以我说 141 是“母题”它的价值不在那 10 行代码而在它背后那套“双指针相对运动 环结构等价于重复”的思维模型。刷题如果只背答案遇到 287 那种包装过的题目会完全懵住理解了模型相当于把一类题都握在了手里。6. 实测对比与刷题心得6.1 两种解法的实测数据我在 LeetCode 上跑过几次最近提交环境波动比较大所以我不太建议过分迷信某个解法的绝对运行时间。但可以从量级感受一下解法时间复杂度空间复杂度在线评测感受适用场景哈希集合O(n)O(n)耗内存略高代码直白第一反应、容易讲解快慢指针O(n)O(1)稳定通过内存占用明显低面试最优解、后续题基础我自己在两个解法之间切换时有个小发现在同样的测试用例下快慢指针的时间波动比哈希大因为它的实际步数取决于相遇点位置常数可能不同但哈希解法要频繁对节点取哈希、查集合常数也不小。整体上两者都在可接受范围选哪个主要看题目有没有空间限制。6.2 给新手的练习路径如果你想用最小成本把这道题真正吃透我建议按这个顺序练先用笔画出三种示例的链表结构标出每个节点的 next 指向。手写哈希解法跑通。手写快慢指针解法跑通并想清楚为什么先移动再判断。用一个小环链表演示快指针追慢指针的过程解释相遇逻辑。写 142用同一套思路找入环点对比 141 只加了几行代码。写 202 或 287感受 Floyd 思想的迁移。我自己的经验是第 4 步最容易卡住因为“相对速度为 1”听起来简单但如果不画图思路很容易飘。我建议你把链表画成一条直线加一个圆环然后把指针位置一步步标出来看它俩怎么逼近一遍就记住了。6.3 面试时的表达顺序如果面试遇到这道题我的建议是先给哈希解法一句话说出思路和复杂度然后立刻说“如果要求 O(1) 空间我有快慢指针方案”再开始写。写快慢指针时最好边说边解释每次移动的含义不要把“slow slow.next; fast fast.next.next”当成不需要理由的魔法。面试官通常想听的解释是快指针每次比慢指针多走一步在环内相对速度恒定所以一定会追上。如果面试官追问“为什么不是走三步”你就可以把 3.2 节的同余分析拿出来说明 2 是保证任意情况下都相遇的最小步长。这一问一答之间你的水平基本就和他的预期对齐了。这道题刷完我不建议你急着刷下一道 Hot100 题而是花十分钟把 142 解决掉。那十分钟的收益比单独刷三道无序的简单题要高得多。