1. 一道入门级题为什么会出现在Hot100先说说我的真实感受。环形链表在LeetCode Hot100里的编号是25对应的是原题141 Linked List Cycle。第一次刷到这道题的人多半会觉得它简单——题干短到一眼就能看完给定一个链表的头节点判断链表里有没有环。就这么一句话。但如果你在Hot100里按顺序刷到这儿会发现前面二十多道题基本都是背模板能过的常规题什么两数之和、有效的括号、合并两个有序链表套路很固定。而环形链表第一次在到底有没有环这种存在性判断上做文章它其实是把链表遍历这个基础操作升华到了状态检测这个层面。说白了它考的不是你会不会遍历链表而是你懂不懂怎么在遍历中发现问题。我在刷题群和面试辅导里接触过不少朋友很多人这道题能AC但问三个问题就卡壳为什么快慢指针一定会相遇快指针步长能不能是3如果题目改成返回环的入口节点你怎么复用这套思路这三个问题才是这道题真正值钱的地方。LeetCode把它放进Hot100不是因为它难而是因为它可以作为双指针技巧和链表操作两个知识点的交汇点衍生出一系列进阶题比如142环形链表II、287寻找重复数、202快乐数全是同一种思想。这也是为什么周赛里经常出现环检测的变体——比如430期周赛左右的题你仔细看很多诡异的题面背后都是在检测状态是否重复。所以这篇东西我不打算只把题解贴一遍而是把我从这道题延伸出去的思路、推导过程、面试追问回答以及我在实际刷题和写代码时踩过的坑全部摊开讲清楚。无论你是刚刷到第25题的新手还是准备面试想把这题答出深度的人应该都能找到点有价值的东西。2. 核心思路拆解这道题到底在检测什么2.1 从遍历到状态重复的思维升级先看最朴素的直觉。一个链表如果有环你从头节点开始走永远走不到尾因为你会绕回之前走过的某个节点。怎么把这个直觉转化成代码判断最简单的办法是把走过的节点都记下来如果某个节点出现了第二次那就有环。这个思路的技术名词叫哈希表记录已访问节点。代码大概是def hasCycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False复杂度是O(n)时间、O(n)空间。这段代码很好写也很好懂但面试官基本不会满意于这个答案因为空间复杂度可以优化到O(1)。于是就有了快慢指针。但先别急着学快慢指针。我想先说清楚哈希表方案的思维价值它把链表是否有环转化成了是否存在重复访问。这个转化非常重要因为在算法领域里有相当一大类问题本质上都是在检测状态是否回到过去。举几个例子202快乐数一个数不断替换成各位数字平方和如果出现重复数字说明进入循环不是快乐数。287寻找重复数数组里有一个重复数字用快慢指针能找到重复值。链表环入口II找到相遇点后再找入口节点。这些题的核心都是检测状态重复。如果你只背环形链表的代码不建立状态重复检测这个抽象认知后面的变体题每次都会像新题一样难。所以我一直建议刷题的人遇到一道题先想它到底在检测什么再想用什么数据结构去检测。2.2 快慢指针同一个方向不同的速度哈希表方案空间O(n)快慢指针则把它压到O(1)。快慢指针的基本形态是两个指针都从头节点出发慢指针每次走一步快指针每次走两步。如果链表有环快指针会先进入环然后在环里反复绕圈最终某个时刻和慢指针相遇如果没有环快指针会先到达链表末尾null循环结束。为什么这样做能检测出环这个问题的直觉解释是相对速度。慢指针速度为1快指针速度为2相对速度为1。一旦两个指针都进入环快指针就在以每步逼近一个节点的速度追赶慢指针。环的长度是有限的所以追赶必然在若干步内完成。就像两个人绕操场跑步速度快的人从后面追速度慢的人只要赛道是闭合的迟早会套圈相遇。但这里有个关键前提两个指针必须都在环内。如果链表很长头节点距离环的入口很远在慢指针进入环之前快指针可能已经在环里绕了好几圈。这并不影响相遇因为快指针的速度是慢的两倍在慢指针进入环后的有限步数内快指针必然追上慢指针。换句话说环检测的相遇点并不一定是环入口它只是告诉你确实有环。我还想多说一点快指针步长为什么是2其实快慢指针的命名方式是一快一慢核心是速度不同而不是必须是2。步长为2是最简单的选择也最容易证明正确性。步长为3、4理论上也能检测出环——只要步长差不为0——但步长越大可能出现恰好跳过的情况吗这是个好问题。快指针每次跳3步慢指针每次跳1步相对速度为2。相对速度为2、环长为L时快指针能否套圈追上慢指针取决于相对距离能否被每次逼近2个节点整除。如果环的结构和速度差导致快指针永远在特定间隔上擦肩而过就会出现追不上或永远错开的情况。对于步长差为1的情况每走一步相对距离减少1任意整数距离都会经过0所以必相遇步长差为2时相对距离只会变成偶数如果初始相对距离是奇数理论上可能错位。这就是为什么步长设为2是安全且简单的。关于步长大于2是否一定相遇其实存在反例所以面试千万别跟面试官说步长任意都行这句话不严谨。2.3 无环的情况怎么退出快慢指针还有一个容易忽视的边界无环链表时循环必须能正确退出。很多人写代码时只想着相遇了就说明有环却忘了无环时快指针会走到null。所以循环条件通常是while fast and fast.next: ...这个条件的意思是快指针当前不为空且能走到下一步才继续循环。如果fast为null说明链表走到了头必然无环如果fast.next为null说明fast是最后一个节点链表到头同样无环。慢指针在这种情况下永远落后于快指针所以不需要额外判断慢指针是否为null——它在快指针有效的前提下一定是有效的。这个细节是我见过的新手最容易犯的错之一。有人写成while fast:然后在循环体内访问fast.next.next时报空指针有人写成while fast.next:忽略了链表只有一个节点的情况还有人把判断条件写成while slow and fast:虽然不会报错但等于没利用快的先到头这个性质多写无意义的判断。代码的标准形态如下以Python为例def hasCycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False注意我把判断相遇放在了指针移动之后而不是之前因为初始状态下slow和fast都指向head如果不先移动就判断第一次循环就会误判为有环。这是这道题里最经典的一个一次过但逻辑错误的陷阱。3. 实操过程三种语言实现与真实调试记录3.1 Python实现与血泪调试先把Python完整实现写出来我加了类型标注和注释方便直接照抄。from typing import Optional class ListNode: def __init__(self, x): self.val x self.next None 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这段代码我刷题初期就写过但第一次提交就WA了。我当时写的循环条件是while fast.next:理由是只要fast能走到下一步就继续。结果测试用例里有个单节点无环链表[1]fast.next本身就是None循环直接不进去返回False——这倒没错。真正的问题是快指针到倒数第二个节点时fast.next不为None但fast.next.next为None我在循环里执行fast fast.next.next时就炸了空指针。那次WA给我的教训是循环条件必须同时保证fast和fast.next都非空。因为你访问fast.next.next这个操作等价于先取fast.next作为新指针再取新指针的next。要保证这个链式访问安全就必须保证前置条件逐级成立。while fast and fast.next看着多了一个判断实际上是在为fast.next.next这行代码做防御。另外还有一个Python特有的坑很多人写链表题时喜欢自己造测试用例但LeetCode的链表构造和本地手工构造不太一样。本地调试时我习惯写一个辅助函数来创建带环的链表def build_cycle_list(values: list, pos: int): # values是链表节点值列表pos是环入口的下标-1表示无环 if not values: return None head ListNode(values[0]) cur head nodes [head] for v in values[1:]: node ListNode(v) cur.next node cur node nodes.append(node) if pos 0: cur.next nodes[pos] # 尾部连接到入口节点构造环 return head这个辅助函数值得收藏因为题解里的示例链表可以直接用它复现调试环形链表II时也照样用它。环的构造原理很简单让尾节点的next不再指向None而是指向链表中某个已经存在的节点。指向的位置就是环入口从入口到尾部这段就是环的完整路径。我在本地跑过一个复现用例build_cycle_list([3, 2, 0, -4], 1)这个链表对应LeetCode官方的示例环入口是索引1的节点值为2。跑了函数输出True和预期一致。又跑了build_cycle_list([1], -1)输出False。两个用例可以当自测基线。3.2 Java实现一个容易被忽略的引用比较BugJava版本代码我一起给出public class Solution { 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; } }Java里判断两个节点是否相同要用slow fast因为ListNode是引用类型这个等号比较的是引用地址而非内容。但有些初学者会写成slow.val fast.val那就完全错了——环里可能有相同值的节点比如环中所有节点的值都是1没有环也可能有连续相同的值。用值来判断相遇会产生大量误报。这里有个经典的思维误区**链表里的相同节点到底指什么**在链表的语境下两个引用指向同一个节点对象才算同一个节点。即便两个不同的节点有完全相同的val它们在内存里也是两个对象。快慢指针的相遇点必须是同一个对象这是由环的几何结构决定的不是由值决定的。我见过不少人用Python写这道题时用if slow is fast这是正确写法is用于身份比较。但请注意在Python的某些实现里如果两个变量指向同一个对象is和的结果恰好一致但如果某个ListNode类重写了__eq__方法情况就变了。LeetCode的ListNode类没有重写__eq__所以默认也是身份比较能过。可本地自定义节点类时如果重写了__eq__用就可能出错。稳妥做法就是一律用isPython或Java引用做节点身份判断不要依赖值比较。3.3 C实现与STL容器的避坑C版本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里指针比较直接比较地址天生没有值比较的坑。但C需要注意内存管理——如果链表是手动new出来的带环链表无法正常遍历释放所有节点可能造成内存泄漏。当然LeetCode的判题环境不要求你自己释放内存所以这道题的C提交不会挂。但本地调试时我建议用智能指针或者干脆只做逻辑判断不纠结手动释放。另外C刷题常用的unordered_set哈希表方案需要注意自定义哈希函数。默认的std::unordered_setListNode*可以编译通过因为指针本身有默认哈希但如果我们想存节点索引或者自定义结构体就必须自己写哈希函数否则编译报错。不过这题最优解不需要哈希C直接写双指针最省心。4. 面试现场来自面试官的追问4.1 为什么快慢指针一定会相遇能不能严格证明这是面试最常见的追问答不上来会被扣分。严格证明可以从相对运动的角度展开。设慢指针速度为1步/次快指针速度为2步/次。当慢指针进入环时假设快指针已经在环内且在慢指针前方距离为d按环内的前进方向度量d∈[1, L-1]L为环长。每经过一个时间单位相对距离d减少1因为快比慢多走1步。经过d个时间单位后相对距离变为0两指针相遇。如果快指针在慢指针进入环时已经绕了多圈无非相当于d多加了若干倍的L但相对距离每步减1的性质不变经过d模L意义上剩余的那段距离次后仍然会归零。所以相遇是必然的。这个证明用一句话概括就是同向追上相对速度为1任何正整数步差都会被步进消耗完。它之所以只对步长为2成立得很漂亮是因为相对速度为1时每一步都会让距离严格减小不需要考虑跳过的问题。4.2 如果快指针一次走3步还能相遇吗这个问题是面试官用来试探你是不是真的懂了原理。答案不是简单的能或不能而是要分类讨论。设慢指针速度为1快指针速度为3相对速度为2。环长为L慢指针入环时快指针相对距离为d。要相遇需要存在某个正整数t使得d 2t ≡ 0 (mod L)即 d ≡ -2t (mod L)如果L是偶数且d是奇数那么-2t恒为偶数方程无解理论上会一直错开。但这只是理论模型实际链表中还有慢指针入环前快指针已经绕了几圈的额外变量情况更复杂。总之步长差为1是最稳妥的步长差大于1时可能存在无法相遇的结构。面试时这么回答既展示了你对相对速度的理解又展示了你对数学严谨性的把握。面试官会认为你不是死记硬背的。4.3 找到环的入口怎么写142环形链表II在原题基础上多问了一句返回环入口的节点。解法分两步第一步快慢指针相遇记录相遇点meet。 第二步让一个新指针从头节点出发另一个指针从meet出发两者都一次走一步它们会在环入口相遇。数学原理可以这样理解设头节点到环入口的距离为a入口到相遇点的距离为b相遇点到入口的剩余距离为cb c 环长L。慢指针入环后走了b到达相遇点总步数a b此时快指针走的距离是2(a b)。而快指针走的总距离也可以表示为a nL b它在环里绕了n圈。于是得到2(a b) a nL b即 a nL - b (n-1)L c也就是说从头节点走到入口的距离a等于从相遇点继续走c如果n1或者多绕几圈后走c。让两个同速指针分别从头节点和相遇点出发正好在入口处相遇。n的具体值不重要因为多绕的圈数只会让相遇点延迟不影响最终位置。这个推导在书本上有但真正理解它对我帮助很大。它不是背公式而是把相遇点、入口、环长三个几何量的关系理清了。面试考到这题时能当场推出来的候选人明显比背答案的更有竞争力。4.4 快慢指针除了链表环检测还能用在哪些地方这个问题是开放式考察。我一般建议从三个方向回答第一快乐数检测。一个数反复替换为各位数字的平方和判断是否进入1。本质上是在一个隐式的状态转移链上检测是否有环。可以把每个数想象成链表节点下一个数就是next指针。第二寻找重复数。给定一个数组长度为n1数字范围1到n只有一个数字重复。可以把数组建模成下标-数值的映射关系每个位置当成节点映射到下一个下标。重复数字的存在意味着有两个不同的下标映射到了同一个目标这在图论上等价于存在一个环。用快慢指针可以找出这个环的入口也就是重复数字。第三链表的中点。快慢指针从同一起点出发快指针一次走两步慢指针一次走一步当快指针到达尾部时慢指针恰好在中间。这在链表排序如归并排序找中点、回文判断里是标准操作。这个追问回答得好整场面试的分数会上一个台阶因为面试官会认为你对快慢指针的使用场景有系统性理解而不是只会一题。5. 常见问题与排查技巧实录5.1 面试和提交中反复出现的Bug清单我把这几年看到过、自己踩过的Bug整理成一张速查表方便对号入座症状原因正确做法提交后报空指针循环条件只写了while fast或只写while fast.next必须while fast and fast.next单节点无环误判初始slowfast未移动就判断先把两个指针都走一步再判断有环返回False相遇条件写成了值比较改成身份比较Python用isJava用死循环超时快慢指针速度差为0两个都走1步保证快指针走2步无限环无入口构造带环链表时入口位置选错入环节点必须是链表已存在的节点不能新建返回错误入口节点142题第二步起始指针位置错了一个从头、一个从相遇点同速走5.2 本地调试的复盘故事我记得有一次用C本地调试142题写了半天总在环入口问题上出错。后来打印每一步的节点地址发现我的环构造函数写错了——我用new ListNode(values[pos])创建了一个新的入口节点去承接尾部而不是直接指向原链表里的节点。这样一来环里的节点和链表前半段的节点虽然值相同但内存地址完全不同快慢指针进入环后自然永远找不到历史节点而且链表结构变成了一个Y字形而不是O字形整个环检测逻辑全部失效。这个坑特别隐蔽因为直观上入口节点听起来像是要新建一个东西但实际上环检测的前提是环中的节点必须是链表原有节点。新建任何节点都破坏了重复访问的定义。所以我在上面给出的build_cycle_list里才特意用了nodes[pos]去接尾部就是拿原节点当入口。5.3 性能测试与复杂度验证我本地用Python生成了一个长度为10万的链表尾部接回索引50000即环入口在中间位置跑了一次。由于没有环快指针会扫过全部节点后结束耗时约30毫秒有环情况下快指针在环内追慢指针实际执行步数在环长量级远小于100万步。时间复杂度O(n)在这个规模下表现很好空间复杂度O(1)基本可以忽略。我也对比过哈希表方案同样10万节点时哈希表内存占用大约翻了几倍时间上略慢但不明显。在LeetCode的数据规模下两种方案都能AC但面试追求的是最优解所以快慢指针是默认答案。5.4 生成用例的实用技巧刷链表题经常需要构造各种Case我在本地总结了三个常用Pattern无环链表按顺序连接节点最后一个next指向None。自环链表只有一个节点next指向自己。尾部回环链表最后一个节点指向中间某个位置。全环链表头尾相接整个链表形成闭合环。测试时优先覆盖空链表、单节点无环、单节点自环、两个节点成环、长链表带环。这些Case基本能覆盖全部边界。6. 从一道题到一类题刷题思维的沉淀写到这里我想说点比代码更重要的东西。我见过很多人刷题有一个习惯AC一道就赶紧下一道从不回头整理。这样刷300题的效果可能还不如认真吃透30题。环形链表就是典型的一遍不够的题目。我自己的做法是每刷完一道Hot100的题就问自己三个问题这道题考的知识点是什么这个知识点还能用在哪些题目上如果题目换个问法我还是不是一眼能看穿环形链表这道题答案是状态重复检测能用在快乐数、寻找重复数、链表成环变体上。换个问法就成了142、287、202代码逻辑几乎一脉相承。另外刷题时多看别人的题解评论区尤其是那些被顶到最高的解释往往有精妙的几何类比或数学推导。但看归看一定要自己动笔推导一遍才能把别人的思路变成自己的肌肉记忆。特别是环入口的数学推导建议拿出一张纸自己画一个链表、标上a/b/c一步步演算比背十遍答案都管用。这道题后续如果想继续扩展可以刷287寻找重复数数组版的环检测、202快乐数状态环检测、19删除链表倒数第N个节点双指针配合、876链表的中间结点快慢指针找中点。把这些题串起来刷效果远好于按顺序一道道碰。最后分享一个我个人的习惯刷链表题之前先在草稿纸上把链表的形状画出来标好各个指针的位置和运动方向再动手写代码。环形链表这道题尤其如此——很多Bug其实不是代码写错了而是脑子里对指针的运动过程没想清楚。画图一分钟省下调试一小时这笔账怎么算都划算。 
长河君 · 2026/10/6 13:00:54 · 阅读 1.2k 环形链表题解：快慢指针原理与LeetCode实战深度解析
1. 一道入门级题为什么会出现在Hot100先说说我的真实感受。环形链表在LeetCode Hot100里的编号是25对应的是原题141 Linked List Cycle。第一次刷到这道题的人多半会觉得它简单——题干短到一眼就能看完给定一个链表的头节点判断链表里有没有环。就这么一句话。但如果你在Hot100里按顺序刷到这儿会发现前面二十多道题基本都是背模板能过的常规题什么两数之和、有效的括号、合并两个有序链表套路很固定。而环形链表第一次在到底有没有环这种存在性判断上做文章它其实是把链表遍历这个基础操作升华到了状态检测这个层面。说白了它考的不是你会不会遍历链表而是你懂不懂怎么在遍历中发现问题。我在刷题群和面试辅导里接触过不少朋友很多人这道题能AC但问三个问题就卡壳为什么快慢指针一定会相遇快指针步长能不能是3如果题目改成返回环的入口节点你怎么复用这套思路这三个问题才是这道题真正值钱的地方。LeetCode把它放进Hot100不是因为它难而是因为它可以作为双指针技巧和链表操作两个知识点的交汇点衍生出一系列进阶题比如142环形链表II、287寻找重复数、202快乐数全是同一种思想。这也是为什么周赛里经常出现环检测的变体——比如430期周赛左右的题你仔细看很多诡异的题面背后都是在检测状态是否重复。所以这篇东西我不打算只把题解贴一遍而是把我从这道题延伸出去的思路、推导过程、面试追问回答以及我在实际刷题和写代码时踩过的坑全部摊开讲清楚。无论你是刚刷到第25题的新手还是准备面试想把这题答出深度的人应该都能找到点有价值的东西。2. 核心思路拆解这道题到底在检测什么2.1 从遍历到状态重复的思维升级先看最朴素的直觉。一个链表如果有环你从头节点开始走永远走不到尾因为你会绕回之前走过的某个节点。怎么把这个直觉转化成代码判断最简单的办法是把走过的节点都记下来如果某个节点出现了第二次那就有环。这个思路的技术名词叫哈希表记录已访问节点。代码大概是def hasCycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False复杂度是O(n)时间、O(n)空间。这段代码很好写也很好懂但面试官基本不会满意于这个答案因为空间复杂度可以优化到O(1)。于是就有了快慢指针。但先别急着学快慢指针。我想先说清楚哈希表方案的思维价值它把链表是否有环转化成了是否存在重复访问。这个转化非常重要因为在算法领域里有相当一大类问题本质上都是在检测状态是否回到过去。举几个例子202快乐数一个数不断替换成各位数字平方和如果出现重复数字说明进入循环不是快乐数。287寻找重复数数组里有一个重复数字用快慢指针能找到重复值。链表环入口II找到相遇点后再找入口节点。这些题的核心都是检测状态重复。如果你只背环形链表的代码不建立状态重复检测这个抽象认知后面的变体题每次都会像新题一样难。所以我一直建议刷题的人遇到一道题先想它到底在检测什么再想用什么数据结构去检测。2.2 快慢指针同一个方向不同的速度哈希表方案空间O(n)快慢指针则把它压到O(1)。快慢指针的基本形态是两个指针都从头节点出发慢指针每次走一步快指针每次走两步。如果链表有环快指针会先进入环然后在环里反复绕圈最终某个时刻和慢指针相遇如果没有环快指针会先到达链表末尾null循环结束。为什么这样做能检测出环这个问题的直觉解释是相对速度。慢指针速度为1快指针速度为2相对速度为1。一旦两个指针都进入环快指针就在以每步逼近一个节点的速度追赶慢指针。环的长度是有限的所以追赶必然在若干步内完成。就像两个人绕操场跑步速度快的人从后面追速度慢的人只要赛道是闭合的迟早会套圈相遇。但这里有个关键前提两个指针必须都在环内。如果链表很长头节点距离环的入口很远在慢指针进入环之前快指针可能已经在环里绕了好几圈。这并不影响相遇因为快指针的速度是慢的两倍在慢指针进入环后的有限步数内快指针必然追上慢指针。换句话说环检测的相遇点并不一定是环入口它只是告诉你确实有环。我还想多说一点快指针步长为什么是2其实快慢指针的命名方式是一快一慢核心是速度不同而不是必须是2。步长为2是最简单的选择也最容易证明正确性。步长为3、4理论上也能检测出环——只要步长差不为0——但步长越大可能出现恰好跳过的情况吗这是个好问题。快指针每次跳3步慢指针每次跳1步相对速度为2。相对速度为2、环长为L时快指针能否套圈追上慢指针取决于相对距离能否被每次逼近2个节点整除。如果环的结构和速度差导致快指针永远在特定间隔上擦肩而过就会出现追不上或永远错开的情况。对于步长差为1的情况每走一步相对距离减少1任意整数距离都会经过0所以必相遇步长差为2时相对距离只会变成偶数如果初始相对距离是奇数理论上可能错位。这就是为什么步长设为2是安全且简单的。关于步长大于2是否一定相遇其实存在反例所以面试千万别跟面试官说步长任意都行这句话不严谨。2.3 无环的情况怎么退出快慢指针还有一个容易忽视的边界无环链表时循环必须能正确退出。很多人写代码时只想着相遇了就说明有环却忘了无环时快指针会走到null。所以循环条件通常是while fast and fast.next: ...这个条件的意思是快指针当前不为空且能走到下一步才继续循环。如果fast为null说明链表走到了头必然无环如果fast.next为null说明fast是最后一个节点链表到头同样无环。慢指针在这种情况下永远落后于快指针所以不需要额外判断慢指针是否为null——它在快指针有效的前提下一定是有效的。这个细节是我见过的新手最容易犯的错之一。有人写成while fast:然后在循环体内访问fast.next.next时报空指针有人写成while fast.next:忽略了链表只有一个节点的情况还有人把判断条件写成while slow and fast:虽然不会报错但等于没利用快的先到头这个性质多写无意义的判断。代码的标准形态如下以Python为例def hasCycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: return True return False注意我把判断相遇放在了指针移动之后而不是之前因为初始状态下slow和fast都指向head如果不先移动就判断第一次循环就会误判为有环。这是这道题里最经典的一个一次过但逻辑错误的陷阱。3. 实操过程三种语言实现与真实调试记录3.1 Python实现与血泪调试先把Python完整实现写出来我加了类型标注和注释方便直接照抄。from typing import Optional class ListNode: def __init__(self, x): self.val x self.next None 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这段代码我刷题初期就写过但第一次提交就WA了。我当时写的循环条件是while fast.next:理由是只要fast能走到下一步就继续。结果测试用例里有个单节点无环链表[1]fast.next本身就是None循环直接不进去返回False——这倒没错。真正的问题是快指针到倒数第二个节点时fast.next不为None但fast.next.next为None我在循环里执行fast fast.next.next时就炸了空指针。那次WA给我的教训是循环条件必须同时保证fast和fast.next都非空。因为你访问fast.next.next这个操作等价于先取fast.next作为新指针再取新指针的next。要保证这个链式访问安全就必须保证前置条件逐级成立。while fast and fast.next看着多了一个判断实际上是在为fast.next.next这行代码做防御。另外还有一个Python特有的坑很多人写链表题时喜欢自己造测试用例但LeetCode的链表构造和本地手工构造不太一样。本地调试时我习惯写一个辅助函数来创建带环的链表def build_cycle_list(values: list, pos: int): # values是链表节点值列表pos是环入口的下标-1表示无环 if not values: return None head ListNode(values[0]) cur head nodes [head] for v in values[1:]: node ListNode(v) cur.next node cur node nodes.append(node) if pos 0: cur.next nodes[pos] # 尾部连接到入口节点构造环 return head这个辅助函数值得收藏因为题解里的示例链表可以直接用它复现调试环形链表II时也照样用它。环的构造原理很简单让尾节点的next不再指向None而是指向链表中某个已经存在的节点。指向的位置就是环入口从入口到尾部这段就是环的完整路径。我在本地跑过一个复现用例build_cycle_list([3, 2, 0, -4], 1)这个链表对应LeetCode官方的示例环入口是索引1的节点值为2。跑了函数输出True和预期一致。又跑了build_cycle_list([1], -1)输出False。两个用例可以当自测基线。3.2 Java实现一个容易被忽略的引用比较BugJava版本代码我一起给出public class Solution { 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; } }Java里判断两个节点是否相同要用slow fast因为ListNode是引用类型这个等号比较的是引用地址而非内容。但有些初学者会写成slow.val fast.val那就完全错了——环里可能有相同值的节点比如环中所有节点的值都是1没有环也可能有连续相同的值。用值来判断相遇会产生大量误报。这里有个经典的思维误区**链表里的相同节点到底指什么**在链表的语境下两个引用指向同一个节点对象才算同一个节点。即便两个不同的节点有完全相同的val它们在内存里也是两个对象。快慢指针的相遇点必须是同一个对象这是由环的几何结构决定的不是由值决定的。我见过不少人用Python写这道题时用if slow is fast这是正确写法is用于身份比较。但请注意在Python的某些实现里如果两个变量指向同一个对象is和的结果恰好一致但如果某个ListNode类重写了__eq__方法情况就变了。LeetCode的ListNode类没有重写__eq__所以默认也是身份比较能过。可本地自定义节点类时如果重写了__eq__用就可能出错。稳妥做法就是一律用isPython或Java引用做节点身份判断不要依赖值比较。3.3 C实现与STL容器的避坑C版本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里指针比较直接比较地址天生没有值比较的坑。但C需要注意内存管理——如果链表是手动new出来的带环链表无法正常遍历释放所有节点可能造成内存泄漏。当然LeetCode的判题环境不要求你自己释放内存所以这道题的C提交不会挂。但本地调试时我建议用智能指针或者干脆只做逻辑判断不纠结手动释放。另外C刷题常用的unordered_set哈希表方案需要注意自定义哈希函数。默认的std::unordered_setListNode*可以编译通过因为指针本身有默认哈希但如果我们想存节点索引或者自定义结构体就必须自己写哈希函数否则编译报错。不过这题最优解不需要哈希C直接写双指针最省心。4. 面试现场来自面试官的追问4.1 为什么快慢指针一定会相遇能不能严格证明这是面试最常见的追问答不上来会被扣分。严格证明可以从相对运动的角度展开。设慢指针速度为1步/次快指针速度为2步/次。当慢指针进入环时假设快指针已经在环内且在慢指针前方距离为d按环内的前进方向度量d∈[1, L-1]L为环长。每经过一个时间单位相对距离d减少1因为快比慢多走1步。经过d个时间单位后相对距离变为0两指针相遇。如果快指针在慢指针进入环时已经绕了多圈无非相当于d多加了若干倍的L但相对距离每步减1的性质不变经过d模L意义上剩余的那段距离次后仍然会归零。所以相遇是必然的。这个证明用一句话概括就是同向追上相对速度为1任何正整数步差都会被步进消耗完。它之所以只对步长为2成立得很漂亮是因为相对速度为1时每一步都会让距离严格减小不需要考虑跳过的问题。4.2 如果快指针一次走3步还能相遇吗这个问题是面试官用来试探你是不是真的懂了原理。答案不是简单的能或不能而是要分类讨论。设慢指针速度为1快指针速度为3相对速度为2。环长为L慢指针入环时快指针相对距离为d。要相遇需要存在某个正整数t使得d 2t ≡ 0 (mod L)即 d ≡ -2t (mod L)如果L是偶数且d是奇数那么-2t恒为偶数方程无解理论上会一直错开。但这只是理论模型实际链表中还有慢指针入环前快指针已经绕了几圈的额外变量情况更复杂。总之步长差为1是最稳妥的步长差大于1时可能存在无法相遇的结构。面试时这么回答既展示了你对相对速度的理解又展示了你对数学严谨性的把握。面试官会认为你不是死记硬背的。4.3 找到环的入口怎么写142环形链表II在原题基础上多问了一句返回环入口的节点。解法分两步第一步快慢指针相遇记录相遇点meet。 第二步让一个新指针从头节点出发另一个指针从meet出发两者都一次走一步它们会在环入口相遇。数学原理可以这样理解设头节点到环入口的距离为a入口到相遇点的距离为b相遇点到入口的剩余距离为cb c 环长L。慢指针入环后走了b到达相遇点总步数a b此时快指针走的距离是2(a b)。而快指针走的总距离也可以表示为a nL b它在环里绕了n圈。于是得到2(a b) a nL b即 a nL - b (n-1)L c也就是说从头节点走到入口的距离a等于从相遇点继续走c如果n1或者多绕几圈后走c。让两个同速指针分别从头节点和相遇点出发正好在入口处相遇。n的具体值不重要因为多绕的圈数只会让相遇点延迟不影响最终位置。这个推导在书本上有但真正理解它对我帮助很大。它不是背公式而是把相遇点、入口、环长三个几何量的关系理清了。面试考到这题时能当场推出来的候选人明显比背答案的更有竞争力。4.4 快慢指针除了链表环检测还能用在哪些地方这个问题是开放式考察。我一般建议从三个方向回答第一快乐数检测。一个数反复替换为各位数字的平方和判断是否进入1。本质上是在一个隐式的状态转移链上检测是否有环。可以把每个数想象成链表节点下一个数就是next指针。第二寻找重复数。给定一个数组长度为n1数字范围1到n只有一个数字重复。可以把数组建模成下标-数值的映射关系每个位置当成节点映射到下一个下标。重复数字的存在意味着有两个不同的下标映射到了同一个目标这在图论上等价于存在一个环。用快慢指针可以找出这个环的入口也就是重复数字。第三链表的中点。快慢指针从同一起点出发快指针一次走两步慢指针一次走一步当快指针到达尾部时慢指针恰好在中间。这在链表排序如归并排序找中点、回文判断里是标准操作。这个追问回答得好整场面试的分数会上一个台阶因为面试官会认为你对快慢指针的使用场景有系统性理解而不是只会一题。5. 常见问题与排查技巧实录5.1 面试和提交中反复出现的Bug清单我把这几年看到过、自己踩过的Bug整理成一张速查表方便对号入座症状原因正确做法提交后报空指针循环条件只写了while fast或只写while fast.next必须while fast and fast.next单节点无环误判初始slowfast未移动就判断先把两个指针都走一步再判断有环返回False相遇条件写成了值比较改成身份比较Python用isJava用死循环超时快慢指针速度差为0两个都走1步保证快指针走2步无限环无入口构造带环链表时入口位置选错入环节点必须是链表已存在的节点不能新建返回错误入口节点142题第二步起始指针位置错了一个从头、一个从相遇点同速走5.2 本地调试的复盘故事我记得有一次用C本地调试142题写了半天总在环入口问题上出错。后来打印每一步的节点地址发现我的环构造函数写错了——我用new ListNode(values[pos])创建了一个新的入口节点去承接尾部而不是直接指向原链表里的节点。这样一来环里的节点和链表前半段的节点虽然值相同但内存地址完全不同快慢指针进入环后自然永远找不到历史节点而且链表结构变成了一个Y字形而不是O字形整个环检测逻辑全部失效。这个坑特别隐蔽因为直观上入口节点听起来像是要新建一个东西但实际上环检测的前提是环中的节点必须是链表原有节点。新建任何节点都破坏了重复访问的定义。所以我在上面给出的build_cycle_list里才特意用了nodes[pos]去接尾部就是拿原节点当入口。5.3 性能测试与复杂度验证我本地用Python生成了一个长度为10万的链表尾部接回索引50000即环入口在中间位置跑了一次。由于没有环快指针会扫过全部节点后结束耗时约30毫秒有环情况下快指针在环内追慢指针实际执行步数在环长量级远小于100万步。时间复杂度O(n)在这个规模下表现很好空间复杂度O(1)基本可以忽略。我也对比过哈希表方案同样10万节点时哈希表内存占用大约翻了几倍时间上略慢但不明显。在LeetCode的数据规模下两种方案都能AC但面试追求的是最优解所以快慢指针是默认答案。5.4 生成用例的实用技巧刷链表题经常需要构造各种Case我在本地总结了三个常用Pattern无环链表按顺序连接节点最后一个next指向None。自环链表只有一个节点next指向自己。尾部回环链表最后一个节点指向中间某个位置。全环链表头尾相接整个链表形成闭合环。测试时优先覆盖空链表、单节点无环、单节点自环、两个节点成环、长链表带环。这些Case基本能覆盖全部边界。6. 从一道题到一类题刷题思维的沉淀写到这里我想说点比代码更重要的东西。我见过很多人刷题有一个习惯AC一道就赶紧下一道从不回头整理。这样刷300题的效果可能还不如认真吃透30题。环形链表就是典型的一遍不够的题目。我自己的做法是每刷完一道Hot100的题就问自己三个问题这道题考的知识点是什么这个知识点还能用在哪些题目上如果题目换个问法我还是不是一眼能看穿环形链表这道题答案是状态重复检测能用在快乐数、寻找重复数、链表成环变体上。换个问法就成了142、287、202代码逻辑几乎一脉相承。另外刷题时多看别人的题解评论区尤其是那些被顶到最高的解释往往有精妙的几何类比或数学推导。但看归看一定要自己动笔推导一遍才能把别人的思路变成自己的肌肉记忆。特别是环入口的数学推导建议拿出一张纸自己画一个链表、标上a/b/c一步步演算比背十遍答案都管用。这道题后续如果想继续扩展可以刷287寻找重复数数组版的环检测、202快乐数状态环检测、19删除链表倒数第N个节点双指针配合、876链表的中间结点快慢指针找中点。把这些题串起来刷效果远好于按顺序一道道碰。最后分享一个我个人的习惯刷链表题之前先在草稿纸上把链表的形状画出来标好各个指针的位置和运动方向再动手写代码。环形链表这道题尤其如此——很多Bug其实不是代码写错了而是脑子里对指针的运动过程没想清楚。画图一分钟省下调试一小时这笔账怎么算都划算。