1. 题目回顾与题意拆解力扣141. 环形链表这道题在热题100里属于会者不难、难者不会的典型。题目描述非常简短给你一个链表的头节点 head判断链表中是否有环。如果有环返回 true没有环返回 false。有环是什么意思链表本来是一条单行道每个节点只指向下一个节点走到最后 next 为 null 就结束了。但如果有环就意味着某个节点的 next 又指回了前面的某个节点形成了一个闭环遍历时永远走不到头。就好比你在一座迷宫里绕圈路一直在重复永远找不到出口。题目还给出了一个额外要求你能不能在不使用额外空间的情况下解决这个问题这句话其实是整道题的灵魂。如果允许开一个哈希表我每次遍历节点的时候把地址记下来发现某个节点地址重复出现那说明有环解法毫无难度。但能否不用额外空间直接提升了这道题的档次让它成为面试高频题中的常客。这道题适合谁刷呢正在备战校招、社招面试的开发者想巩固链表基本功的初学者以及复习双指针技巧的老手都值得把这道题吃透。别觉得它简单环形链表相关的变形题一共有六七个后面的 142 环形链表 II、287 寻找重复数、202 快乐数、160 相交链表本质都能和这个题扯上关系。把 141 讲明白等于给后续一大片题目打了地基。我第一次刷这道题的时候其实走了不少弯路。看到题干第一反应是用哈希表不就行了结果写完被空间复杂度卡住后来想用遍历计数超过 N 就判定有环这种歪招又被边界情况坑了一把。等真正理解了快慢指针才意识到这道题其实是在考你两个东西一个是环这个结构和追及问题之间的关系另一个是在极端条件下把思路做干净的工程能力。2. 四种解法思路与选型分析2.1 暴力遍历计数法最直觉但不可靠的解法初学者最容易想到的方案是这样的维护一个计数器遍历链表每走一步 count如果 count 超过链表总长度说明有环。因为一个没有环的链表遍历次数最多等于节点数走到头就是 null只要节点数有限遍历次数不可能超过节点数。这个思路在实际工程里有一个致命问题链表总长度怎么拿如果是带头节点的链表预先遍历一次求长度再把计数器方案跑一遍等价于两次遍历时间上不划算。如果不知道长度就根本没法判断超过多少才算异常。你说我设置一个比较大的阈值比如 10 万但链表本身有 20 万个节点呢没环也会误判。反过来一个环形链表只有 5 个节点你阈值设太大判断就有明显延迟。更麻烦的是这种解法隐含了一个假设我可以任意遍历如果链表节点结构本身是只读的你连打标记的机会都没有。所以在 LeetCode 这种测评环境里暴力计数法属于能过测试但毫无价值的方法。面试官看一眼就知道你没有掌握空间复杂度的概念这题基本就浪费了。2.2 哈希集合法正确但不够优雅第二种方案就是哈希集合这也是最容易想到的正解之一。用一个 Set 存储已经访问过的节点遍历链表时每到一个节点就检查它的地址是否已经存在于集合中如果在说明回到了之前的节点链表有环如果 alive 直到遇到 null说明链表无环。这个思路的正确性没有争议时间复杂度 O(n)空间复杂度 O(n)。在力扣上的评分也是完全 AC 的。问题在于题目那句你能不使用额外空间解决吗直接把你逼向更优解。面试时如果你只给出哈希集合方案面试官大概率会追问一句能不能把空间复杂度降到 O(1)然后就看你能不能接住这个话头了。哈希集合方案还有一个容易被忽略的注意点如果链表节点值相同但地址不同集合判断的是地址不是值。说人话就是两个节点值都是 3一个在链头一个在链尾这不算环。因为你比较的是节点对象本身不是节点里的值。有些新手把 val 存进集合就会得出完全错误的结论这是非常经典的踩坑点。2.3 快慢指针法O(1) 空间的标准答案快慢指针也叫 Floyd 判圈算法这个方案才是题目真正想让你写的。它的思路特别简单定义两个指针slow 每次走一步fast 每次走两步。如果链表没有环fast 会先走到 null如果链表有环fast 一定会追上 slow两个指针在环内相遇。你可以在纸上画一个有环的链表模拟一下fast 进入环以后相当于在环形跑道上追 slow。因为 fast 每一步比 slow 多走一格在环内每走一次两者的相对距离就缩短 1所以迟早会追上。这就是中学数学里的追及问题只不过把跑道搬到了链表上。代码实现也非常短特别适合背下来当作肌肉记忆。但注意边界条件极其容易翻车。很多人的快慢指针代码写成这样# 错误示范 while fast and slow: slow slow.next fast fast.next.next这段代码有两个问题。第一循环条件如果只判断到 fast 和 slow 存在那么倒数第二步 fast.next 已经是 null再执行 fast.next.next 会直接抛空指针异常。第二如果 slow 走到了环里的某个节点fast 正好越过它两个指针会不会错过这里需要仔细推演不会错过。因为 fast 每轮相对 slow 的位移是 1 个节点任何整数的相对距离都会在有限步内被缩小到 0所以必有相遇。正确写法应该是while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False这个 while 条件的顺序也有讲究必须先判断 fast 再判断 fast.next因为一旦 fast 为 Nonefast.next 就不存在了。为什么不需要判断 slow因为 fast 走得快如果链表有尽头先触底的一定是 fastslow 永远在 fast 后面不会先于 fast 变成 null。2.4 递归标记法与内存特性不推荐但有价值的思路还有一些碎碎念的解法比如在节点结构允许的情况下打标记。如果节点对象有一个 visited 字段遍历时把 visited 改成 True如果再次遇到 visited 为 True 的节点说明成环。这个方法空间复杂度是 O(1)因为打标记是在原节点上操作。但这样说其实是在作弊现实生活中你拿到的链表节点未必有 visited 字段面试官不给机会改结构这个方法就废了。还有一种非常取巧的做法在遍历时把每个节点的 next 改成指向一个哨兵节点如果后面又访问到这个哨兵说明有环。这个思路是对的但修改了原始链表结构属于破坏性操作。实际工程中链表往往承载着业务数据改结构会造成不可预知的后果。所以这类方法我一般只在掌握标准解法之后当作思维拓展来提一嘴不会推荐在代码里用。说到底四种解法对比下来真正值得练的就是哈希集合和快慢指针两种。哈希集合是用空间换时间的典型代表快慢指针是用数学换空间的经典案例。能把这两种思路都写出来并且解释清楚为什么快慢指针不会错过这道题才算真正吃透了。3. 快慢指针的数学原理与工程细节3.1 为什么慢指针一步、快指针两步是最优配置面试的时候经常有面试官会追问为什么 slow 走一步、fast 走两步如果 fast 走三步行不行这个问题其实挺有深度的。先说结论fast 走两步是工程上最稳妥的选择fast 走三步理论可行但实现容易出错。原因是这样的fast 每步比 slow 多走 k-1 个节点其中 k 是 fast 的步长。fast 走两步时每轮相对距离减少 1不会跳过 slow。但如果 fast 走三步每轮相对距离减少 2当两者距离为 1 时fast 一轮就越过了 slow这个越过不代表相遇因为 fast 走的是 next.next.next 这种跳转不会停留在 slow 所在的中间节点上。那是不是走三步就一定不行也不是。如果环足够长fast 多走几圈总有机会重新追上。但从代码严谨性角度看走两步是保证必相遇的最小步长写起来也最干净。走三步虽然也能跑但你需要额外证明始终会在某个时间窗口内相遇这个数学推导你要在面试现场讲压力不小。真正见过世面的面试官不会因为你走三步而加分反而可能觉得你在炫技所以我建议老老实实走两步。还有个细节是链表的节点数有限若环长为 Lslow 进入环后fast 已经在环内某处。每轮相对距离减 1所以最多 L-1 轮后必然相遇。这个性质保证了时间复杂度为 O(n)而不是 O(n²)。另外fast 在无环链表中先到达 null所以循环以 fast 为判空条件这也是快指针负责探路的工程语义。3.2 环节点定位从 141 到 142 的自然延伸141 只要求判断是否有环142 要求找出环的入口节点。这一对题目经常一起出现面试时你答完 141 之后面试官大概率会让你把这层也讲出来。判定有环之后如何找入口结论是一个简单到惊人的公式快慢指针相遇后让其中一个指针回到头节点另一个留在相遇点然后两个指针都每次走一步再次相遇的位置就是环的入口。这个结论的证明可以这样想假设链表头到环入口的距离是 a环入口到相遇点的距离是 b相遇点再绕到入口的距离是 c。因为环长 b cslow 走了 a b 步fast 走了 a b n*(bc) 步其中 n 是 fast 在相遇前绕的圈数。又因为 fast 走的总步数是 slow 的两倍所以有a b n*(bc) 2*(a b)整理得到 a (n-1)*(bc) c。这个等式说明从链表头走到入口的距离等于从相遇点绕着环走若干圈回到入口的距离。所以两个指针同步前进必在入口汇合。这类推导不需要背但建议自己画个图推一遍。你画三个节点a 取 1、b 取 1、c 取 1代入公式形象思考一个从头部出发、一个从相遇点出发为什么碰面一定在入口理解了就再也不会忘。3.3 时间复杂度与空间复杂度到底怎么算很多人一看到快慢指针下意识觉得最坏情况 fast 要跑很多圈时间复杂度是不是 O(n²)。这是一个很普遍的误解。其实可以通过一个简单的委托来计算slow 进入环时fast 已经在环中。由于二者速度差为 1最糟糕情况下 fast 刚错过 slow 一个身位那也要走 L-1 步相遇L 是环的长度。而 slow 进入环之前最多走 n 步n 为链表总节点数。所以总步数 n L O(n)空间复杂度是 O(1)。哈希集合方案的时间复杂度也是 O(n)但空间是 O(n)。两相对比快慢指针明显更香。不过哈希集合也有它的优势好理解、不易写错适合面试时间紧张、对手写代码不熟悉的新人保底快慢指针则需要一定的数学基础写错边界条件的概率更高。所以我的建议是先写哈希集合保证 AC 有底气再背快慢指针追求空间最优。4. 代码模板与边界用例解析4.1 Python 实现与逐行注释这道题的 Python 解法非常简单但细节决定成败。我平时刷题用 Python 版本如下class ListNode: def __init__(self, x): self.val x self.next None class Solution: def hasCycle(self, head: Optional[ListNode]) - bool: slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False第 1 行到第 4 行是链表节点的定义不解释。第 6 行定义 hasCycle 方法接收链表的头节点。第 7 行把 slow 和 fast 都初始化成 head这个是关键。有些写法会把 fast 初始化成 head.next那样也可以但需要额外处理 head 为 None 的情况。统一初始化成 head 可以少写一个 if。第 9 行的 while 条件fast and fast.next是边界条件的核心。如果链表只有一个节点fast 指向该节点fast.next 是 None循环直接跳过返回 False。如果链表为空fast 是 None循环也直接跳过。这两个边界情况不用单独写 if代码就简洁了。第 10 行 slow 往前走一步。第 11 行 fast 往前走两步。注意顺序先走再判断。如果先判断再走初始时 slow 和 fast 都指向 head你就会误判为有环这是一个极其愚蠢但很容易犯的错误。第 12 行判断两个指针是否指向同一个地址。这里一定要用地址相等不要用 val 相等。我之前见过有人写if slow.val fast.val:这在小数据里可能碰巧通过但实际是完全错误的。因为两个不同节点可以存储相同的值这并不代表有环。4.2 C 实现与指针操作注意点如果你的主力语言是 C刷这道题的写法更接近底层指针操作坑也多一些/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { ListNode* slow head; ListNode* fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; } };C 里要注意的是fast-next-next只有在fast-next不是 nullptr 的情况下才能安全访问这就是为什么 while 条件里必须先写fast ! nullptr再写fast-next ! nullptr。如果你把两个条件写反了遇到偶数长度无环链表时最后一步会访问空指针。LeetCode 的判题系统里空指针访问会直接报 runtime error不算超时是整个测试用例弹出。还有一点当链表没有环时fast 会先走到链表末尾此时 slow 可能才刚到链表中间位置。循环结束返回 false这不需要 slow 走到 null。所以不要额外判断 slow否则就是多余操作。4.3 必须亲手验证的边界测试用例很多人在本地写算法题都是写完就跑一遍示例AC 了就不再管这在简单题里问题不大但遇到 141 这种细节题最好自己构造几个边界用例再提交。我每次刷链表题都会用以下套路来验证测试场景链表结构预期输出设计意图空链表head Nonefalse排除空指针访问单节点无环[1] 且 nextNonefalse排除单节点循环判断双节点无环1-2-Nonefalse排除 fast 到倒数第二节点时的空指针双节点成环1-2-1true验证快慢指针的最短相遇路径长环单节点入口1-2-3-4-2true验证环内追赶逻辑全链条成环1-2-3-1true验证 head 即入口的场景我建议你把这些用例一个个手动模拟不要只依赖代码运行结果。比如双节点成环的用例slow 和 fast 都从 1 号节点出发第一轮后 slow 到 2 号fast 也到 2 号二者相遇返回 true。这个模拟能帮你确认循环条件和步进顺序是否正确。我自己在本地调试时还喜欢写一个辅助函数把链表打印出来虽然 LeetCode 上链表没有漂亮的 to_string但本地构造结构再输出节点下标能直观看到 fast 的轨迹。这个方法在调试更复杂的链表题时非常管用。5. 关联题目与面试追问方向5.1 环形链表变形题全家桶141 是环形链表的入门题真正进阶的题目其实有很多亲戚。我在刷力扣热题 100 时发现环形链表的亲戚渗透在各个序列里环形链表 II不只判断有没有环还要求返回环的入口节点。解法上文已经给出了关键是记住第二次同步走的招数。寻找重复数给定一个包含 n1 个整数的数组每个数在 1 到 n 之间至少有一个重复的整数。这个问题可以转换成找环入口。把数组下标看成链表节点nums[i] 看成 next 指针因为有重复数所以必然出现环。这个转换是二进制题里最漂亮的场景之一能想到的人很少想通了就一通百通。快乐数不断把各位数字平方求和如果最后变成 1 就是快乐数如果陷入循环就不是。这题本质上也是判断链表是否有环数字 n 是节点n 的下一个节点是它的各位平方和。只要在循环中发现某个数出现两次就说明走进了死循环。用哈希集合能做但用快慢指针更优雅。相交链表这个题不涉及环但同样用双指针技巧。两指针分别遍历两条链表走到头后换到另一条链表的头继续走相遇处就是交点。这个思路与快慢指针的相对速度差同源但解题逻辑完全不同值得放在一起对比记忆。5.2 面试追问如何证明环的存在性面试官问完题后大概率会追加一些问题我根据自己和朋友的面试经验整理了几个最高频的追问方向为什么快指针速度是慢指针的两倍不是三倍这个问题前面已经讲了回答的核心是两倍时可以保证每轮间距减少 1不存在跳过slow节点的偶发情况再加上一句实现最简洁就够了。如何证明两个指针一定在环内相遇而不是在环外这个问题的答案是fast 如果先到环入口然后在环内打转slow 进入环后两者都在环内此时才可能相遇。所以相遇点必然在环内不会出现在链表头到环入口的那段直线上。如果链表非常大比如百万级别快慢指针会不会溢出这里要注意LeetCode 的评测环境里一般不会真的访问百万级别的超长链表但在工程里即使链表很大fast 和 slow 的操作也只是指针移动不涉及递归调用不会有栈溢出问题。唯一需要注意的是如果 fast 在无环链表里跑得太快而链表又异常巨大可能会耗时较多但仍然是线性复杂度。追问 142 的入口求解时能不能用哈希集合顺便找到入口答案是可以哈希集合记录第一圈访问的节点当遇到第一个重复节点时那个节点就是入口。这个方案的时间复杂度和空间复杂度都是 O(n)面试时可以作为退而求其次的方案提出来。5.3 这道题的工程启发从算法到系统设计有人觉得刷链表题对工作没有直接帮助我不同意。环形链表这种问题在真实工程项目里其实随处可见文件系统里的循环目录引用、网络报文环路检测、数据库外键关系成环、依赖解析器里的循环依赖检测本质上都是判断一个图或者链结构有没有环。你能写好 141说明你对图论里的环检测有基本认知面试官问一些系统设计题的时候你就可以把快慢指针的思想迁移过去。举个例子我们在处理依赖关系时经常需要检测循环依赖比如 A 依赖 BB 又依赖 A。如果依赖图非常深用 DFS 配合三色标记法是最常规的方案这本质上也是发现重复访问的思路。而如果业务数据是一个超长链表结构你不想额外开辟内存做标记快慢指针方案就有它的用武之地。我负责过一个配置中心模块配置项之间可以互相引用当时就是用类似快慢指针的思路处理循环引用的代码量小而稳定。6. 高频易错点与实操排坑实录6.1 我在提交记录里翻出来的几个典型错误这道题是我刷力扣早期碰到的当时提交了三次才 AC留了不少惨痛教训。每次有人问 141我都愿意把这三个坑拿出来讲第一个坑是 while 条件的空指针。我最开始的写法是while fast.next and fast.next.next看起来没问题但实际上如果 fast 已经是 None访问 fast.next 会直接炸。正确姿势先检查fast本身存在再访问它的 next。LeetCode 报错信息通常是AttributeError: NoneType object has no attribute next看到这个报错基本就是这里的问题。第二个坑是把 slow 和 fast 的初始位置都设在 head然后进循环先判断相等结果上来就返回 True。这个问题很蠢但程序跑出来的结果确实会让你怀疑人生。正确做法一定是先移动再判断除非你人为构建一个slow 比 fast 慢一步的起始状态。第三个坑是误用值相等替代地址相等。比如链表 1-1 无环head 的 val 是 1第二个节点的 val 也是 1你用if slow.val fast.val会在某个瞬间判断为相等返回 True但链表其实无环。这种错误在节点值高度重复的测试用例里几乎必现。判断是否相遇的唯一标准就是slow is fast也就是地址相等。6.2 测试用例设计习惯写题之前先写列子我在刷题后期养成了一个习惯不管什么题先把测试用例列出来再动手写代码。这种方法对链表题尤其重要因为链表题不像数组题可以直观比较输入输出它绕来绕去指来指去脑内推演容易出错。以 141 为例拿到题我先把上表里的六个用例写在一个文本文件里然后逐个模拟。模拟方式不是看代码而是在纸上画链表结构给节点编上序号用箭头模拟 slow 和 fast 的位置。这个过程看着原始但对理解快慢指针帮助极大特别是理解为什么 fast 走两步就一定相遇这个问题时纸笔推演远胜于默读代码。后来我写 142 的时候这个习惯直接救了我。当时我始终想不明白为什么二次相遇点就是入口于是画了一个 1-2-3-4-5-3 的环形结构从头开始走一遍再用公式推导一遍才彻底开窍。如果你也卡在这一类问题上放下键盘先纸上推演十分钟。6.3 从 141 到信手拈来的境界当你把 141 的哈希集合和快慢指针都写熟之后这道题对你来说应该像条件反射一样看到环形链表四个字手指就已经在键盘上跳舞了。我给你的目标是闭着眼睛能写出快慢指针的骨架当面试官问为什么能相遇时你能利索地讲出相对速度差逻辑而不是支支吾吾说我背的模板。做到这个程度你就可以继续往下刷 142、287、202 这些延伸题了。我自己刷题时经常感叹一道简单题背后延伸出去的知识树比单纯刷十道孤立题目还有价值。141 就像一个分叉路口往左走是哈希表思维往右走是双指针思维往上走是图论环检测往下走是数学追及。你能从这道题里吸收多少营养完全取决于你用多少心思去理解它的原理而不只是 AC 掉它。建议你刷完 141 后顺手把 142 也写了再对照着看 287 的官方题解。这三道题放在一起练基本就能把判断环、找入口、数字环转换这三个层次打通。打通之后环形链表这一支的题目你基本可以横着走了。