先讲一个我实际遇到过的情况。有次做模拟笔试我写了一个链表反转手写样例全过提交上去直接超时。当时完全懵后来把链表演算了一遍才发现测试数据里某个节点的 next 指回了之前的节点整个链表成了环。程序在 while 循环里出不来跑多久都是超时。碰过头之后我才真正重视这类题第141题“环形链表”问的就是这件事给定链表的头节点判断链表中是否存在环。这道题在题库里属于“看着简单、坑却不少”的代表。它考的不只是你会不会写两个解法还考察你对边界条件的敏感度、空间复杂度的取舍以及对一个经典算法思想——快慢指针也叫龟兔赛跑——的理解深度。这篇文章我从题面拆解开始把哈希表法和快慢指针法都过一遍包括相遇证明、常用陷阱、面试追问变形以及判环思想在真实系统里的应用。不管你是刚开始刷链表题的新手还是准备面试想查漏补缺的老手都能在这里找到可以直接拿去用的结论。1. 题面拆解判断链表成环到底在考什么1.1 题面描述与隐含信息原题的描述很简短给出一个链表的头节点 head判断该链表中是否有环。返回一个布尔值即可。但这里有一个容易让新手困惑的点题目描述里往往会提到一个 pos 参数表示尾节点 next 指针指向的节点索引从 0 开始如果 pos -1 则表示无环。很多人在提交代码时会下意识去找这个 pos 传进来结果发现函数签名里根本没有这个参数。原因很简单pos 只是题目在可视化环境里用来构造测试链表的参数不需要也不应该出现在你的解法函数里。你要做的只是拿到一个已经是“既成事实”的链表去判断它到底成环没有。要理解“环”的本质可以把链表想象成一张单向通行图。每个节点只有一条出边也就是 next。如果某个节点的 next 指向了自己或者指向了它前面的某个节点你就永远无法沿着 next 走到 null。此时链表不再是“链”而是一个带尾巴的圈。常见的三种测试形态需要心里有数普通链表每个节点最终指向 null无环。尾部接回中间节点这是最典型的环比如 1-2-3-4-2。自环一个节点的 next 指向它自己环长为 1。第三种情况最容易在代码里翻车。如果你写的循环条件是while (node ! null) node node.next;且不记步数遇到自环直接死循环。判环算法本质上就是要在不牺牲这种遍历能力的前提下把死循环变成可判定的逻辑。1.2 边界情况越简单越容易翻车很多时候一个解法本身不难难的是边界条件。这道题的边界集中在三种情况head 为空。只有一个节点且 next 指向 null。只有一个节点且 next 指向自己。我把这三种情况列成一张表方便你对照检查自己的代码输入形态是否有环快慢指针能否检测head null否能循环条件直接不满足返回 false单节点1 - null否能fast 走到 null返回 false单节点1 - 1是能快慢指针会相遇多节点尾部指回中间是能慢指针入环后必被追上从表格能看出一个健壮的解法必须显式处理空链表。否则你会在fast.next上直接读到空指针异常。这个细节是面试中最常见的减分项。1.3 为什么这道题是高频题环形链表在面试里高频出现原因不是它知识点有多深而是它特别适合考察“算法思维分层”。第一层能不能想到用哈希表记录遍历过的节点第二层能不能把空间压缩到 O(1)第三层能不能把快慢指针的相遇原理讲清楚并延伸到找环入口。更重要的是这个题是后续一堆链表问题的地基。比如环形链表 II 要求返回环的入口节点相交链表可以用判环思路间接求解还有一类“判断链表中是否存在无限循环”的系统级问题本质也是同一套思想。你把 141 吃透了后面那些题会轻松很多。2. 哈希表方案最直觉的解法为什么只是及格分2.1 核心思路与实现代码最直观的想法遍历链表每经过一个节点就把它记下来。如果后面某个节点已经出现过了就说明这条路走回了之前的地方链表成环。这里有一个关键点记录的是节点本身而不是节点的值。我之前见过有人用setint存节点的 value这是错的。环形链表题里不同节点的值可以完全相同比如 1-2-3-2-3 这种用值判断会误判而节点对象本身在内存里有唯一的地址用它作为 key 才是可靠的。Python 参考实现def hasCycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return FalseC 参考实现class Solution { public: bool hasCycle(ListNode *head) { unordered_setListNode* seen; ListNode* cur head; while (cur) { if (seen.count(cur)) return true; seen.insert(cur); cur cur-next; } return false; } };unordered_setListNode*存的是指针也就是节点的内存地址。只要同一个节点被二次访问地址必然相同判断准确。2.2 为什么面试官不会止步于这个答案哈希表法能跑过绝大多数在线评测时间复杂度和空间复杂度分别是 O(n) 和 O(n)。如果你面试时直接给出这个解法面试官通常会点头然后追问一句“能不能把空间复杂度降到 O(1)”被这么问不丢人因为 O(n) 空间的方案存在的意义主要是给思路做铺垫。在真实系统里链表可能非常长几百万个节点并不稀奇。如果每次判断成环都要开一个等规模的哈希表内存开销不可接受。更典型的是你需要判断的链表可能本身就在一个内存紧张的环境里比如嵌入式设备或者某个被压到极限的服务进程。这时候 O(1) 空间不是优化而是硬性要求。另外哈希表方案还有一个隐含陋习它“记住一切”。判环其实只需要判断“是否回到已经走过的节点”并不需要知道所有走过的节点。当你意识到这一点就会自然地思考有没有一种方式只用两个指针不记账也能判断2.3 空间权衡的实战意义我在写工程代码时对空间复杂度的敏感度比刷题时更高。哈希表法在 LeetCode 这类环境里很舒服因为测试用例规模有限。但你要是在一个高并发服务里给每个请求都开一个unordered_set去检测一个可能几百万节点的链表GC 压力和内存峰值都会让你很难受。所以我的建议是哈希表法可以作为“解释为什么需要优化”的引子但最终实现应该落到快慢指针上。面试时如果时间充足最好先把哈希表思路说一遍再过渡到 O(1) 空间解法这样能展示出你的复杂度意识。3. 快慢指针Floyd 判圈从直觉到严格证明3.1 龟兔赛跑的思想快慢指针的昵称叫龟兔赛跑。你让两个指针同时出发慢指针乌龟每次走一步快指针兔子每次走两步。如果链表没有环快指针会先一步到达终点 null如果链表有环快指针会在环里一圈圈地跑最终在某个节点追上慢指针。这个思想听起来像脑筋急转弯其实它对应的是一个成体系的判圈算法。算法的名字可能因人而异但核心逻辑很统一两个不同速度的指针在同一个结构上运动如果结构存在循环快的那个必然撞见慢的那个。为什么是“必然”直觉上环是一个封闭赛道兔子比乌龟快那么兔子总会追上乌龟。但如果你真的去实现会发现有一些微妙的前提条件需要证明才能放心使用。3.2 证明为什么两个指针一定相遇设从 head 到环入口的步数为 a环内节点数为 L。让慢指针和快指针同时从 head 出发慢指针速度为 1快指针速度为 2。慢指针到达环入口时一共走了 a 步。此时快指针已经走了 2a 步其中在环内已经转了 a 步。也就是说快指针在环内的位置相当于从入口前进 a 步的位置。对它当前相对入口的距离取模就是 a mod L。如果 a mod L 0说明快指针正好也在入口两个指针在这一刻就已经相遇检测结束。否则设 d a mod L快指针在慢指针前方 d 步的位置。沿着前进方向看快指针和慢指针之间的“追赶距离”是 L - d。接下来每一轮循环慢指针前进 1快指针前进 2两者的距离差减少 1。因为追赶距离 L - d 是一个小于 L 的正整数所以最多经过 L - 1 轮快指针就能追上慢指针。这个结论非常关键慢指针在环内不需要走满一整圈就会被追到。所以总循环次数大约是 a 加上不超过 L 的追赶步数即 O(a L)而 a L 不会超过链表总节点数 n 的量级。这就是为什么快慢指针判环的时间复杂度可以被证明为 O(n)并且不会出现无限循环。3.3 三种语言实现最常见的写法让 fast 初始也指向 headdef hasCycle(head): if not head: return False slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False注意这段代码在移动指针之后才比较所以不会出现“初始时 slow fast 导致误判”的问题。C 版本class Solution { public: bool hasCycle(ListNode *head) { if (!head || !head-next) return false; ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; } };这里我先检查head和head-next避免后续对空指针解引用。实际上不写if (!head-next)也能运行因为while (fast fast-next)会兜底但显式处理更容易读。Java 版本public boolean hasCycle(ListNode head) { if (head null) return false; ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) return true; } return false; }三种语言的逻辑完全一致只是语法糖不同。核心就是一句fast每走两步slow走一步相遇即返回 true。4. 快慢指针的边界条件最容易白给的三个坑4.1 快指针从 head 走还是从 head.next 走网上很多代码会让 fast 初始化为head.next而慢指针初始化为 head。这样写本身没问题但会带来一个连锁反应循环条件里必须更早地判断fast和fast.next是否为空。我见过不少初学者把fast head和while (fast fast.next)组合错也见过把fast head.next和while (slow ! fast)组合错结果要么空指针要么死循环。我的建议很简单统一用fast head的初始化。这样 while 循环条件写起来最自然只要fast和fast.next都非空就继续走。判断顺序记住一条先判断fast本身再判断fast.next因为后者依赖前者存在。两种初始化对比初始化方式循环写法注意点slow head; fast headwhile (fast fast.next)移动后再比较最推荐slow head; fast head.nextwhile (slow ! fast)循环内要判空容易漏如果你选择第二种循环里必须在移动前检查fast和fast.next是否为空否则访问fast.next.next会直接崩溃。相比之下第一种写法更优雅也不易出错。4.2 步长选 2 还是选 3有人会问快指针一次走三步行不行答案是行但在面试里不建议。原因有三个。第一步长为 2 时快指针相对慢指针的速度差正好是 1。这意味着每一轮循环两个指针之间的距离稳定缩短 1 步绝对不会“跳过去”导致思想上的纠结。虽然数学上步长为 3 也能追上但证明时要处理相对速度差为 2 的情况追及轮次可能更多边界条件也更脆。第二步长越大快指针越容易提前碰到 null。在无环链表上步长 2 已经让快指针承担了提前结束的任务步长 3 会让这种“提前触底”在代码里更难预判。第三面试官真正想听的往往不是一个更花哨的步长而是你能解释清楚步长 2 的工程折中速度差最小逻辑最简单数学证明最直观。你如果能说出“2 是相对速度等于 1 的最小步长”面试官会觉得你对细节是真懂。4.3 终止条件循环判空的正确写法这道题最容易的翻车点不是理解错而是空指针异常。常见的错误版本长这样while fast.next and fast.next.next:如果fast本身是 None你连fast.next都访问不了。所以正确顺序一定是while fast and fast.next:先保证fast存在再访问它的 next。同理fast fast.next.next这行代码只有在fast.next非空时才安全。把它放在 while 条件里已经保证了就不会出错。再补充一个实际测试时很有用的技巧如果你手头有个可能成环的链表又不想写完整判环代码可以先在循环里加一个计数器最多走 n 步就退出。这种“预防式护栏”在真实 debug 里非常管用哪怕最后定位到的问题不是环也至少能避免把开发环境跑挂。4.4 自环的特殊情况自环是head.next head。这种情况下两个指针都从 head 出发第一次移动后 slow head.next也就是 headfast head.next.next也是 head两者相等返回 true。逻辑没问题。但我见过有人在这种形态上栽跟头原因是用了哈希表解法却记录了“节点的值”。如果 head 的值恰好和后续某个节点值相同就会误判为有环。所以我再强调一遍哈希表务必存节点对象或指针不要存值。5. 面试追问从“有没有环”升级到“环的入口在哪”5.1 环形链表 II 的考法第 141 题只要求返回布尔值但面试官通常会接着问如果链表有环请返回环的入口节点如果没有环返回 null。这就是环形链表 II 的考法。先想一个简单但算出错的方法用哈希表遍历时第一个重复遇到的节点就是入口。因为当你第二次经过某个节点时它就是环的起点。这个解法正确但空间复杂度是 O(n)。面试官大概率会要求你继续优化到 O(1)。5.2 相遇点与入口的关系推导要找到入口得把前面证明里的式子再推进一步。设慢指针从 head 走到相遇点总步数记为 a x其中 a 是 head 到环入口的步数x 是慢指针从入口进入环后到相遇点之间走的步数。因为快指针速度是慢指针的两倍所以快指针总步数是 2(a x)。两指针步数差为 a x而这个差值正好是快指针在环内比慢指针多绕的圈数记为 kL。于是得到a x kL这个等式是找入口的钥匙。把它改写成 a kL - x。这个式子的几何含义是从相遇点继续往前走 a 步你会恰好回到环入口。因为 kL - x 相当于绕了 k 圈后再倒退 x 步而倒退 x 步正是从相遇点回到入口的距离。所以解法是在第一次相遇后把一个指针重新放回 head另一个留在相遇点。两个指针都改成一次走一步。当 head 出发的指针走过 a 步到达入口时相遇点的指针同样走了 a 步正好也停在入口。两者再次相遇的位置就是环入口。代码实现def detectCycle(head): fast slow head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: slow head while slow is not fast: slow slow.next fast fast.next return slow return None这个解法的空间复杂度仍然是 O(1)时间还是 O(n)。你在面试里如果能把这个推导过程完整讲出来含金量比背十道题都高。5.3 顺带说说“环的长度”找到入口之后环的长度就很好算了从入口出发沿着 next 一直走再次回到入口时的步数就是环长 L。这个操作也需要一个计数变量并且注意要先移动再计数避免上来就把入口算成 0。如果你不知道入口只知道相遇点也可以数环长从相遇点出发继续一路 next回到相遇点时的步数同样是 L。因为在环内任意节点作为起点走一圈回到自身的步数都是 L。面试官还可能在追问里问“能不能在一次遍历同时求出环长和入口”这个通常不需要你现场实现把思路讲清楚就行先用快慢指针判环并得到相遇点再走一圈数出环长最后用 5.2 的双指针法找入口。每一步的复杂度加起来依然是线性的。6. 判环思想在真实系统里的用武之地6.1 对象图与循环引用检测我最早觉得判环算法只能用来做题后来维护老项目时才发现它在真实系统里的用处比想象中大得多。比如某些语言在垃圾回收时需要对对象图做可达性分析。对象之间的引用如果形成了环一个简单的递归遍历就会无限递归。虽然现代回收器会用三色标记等手段避免无限循环但“检测对象图是否有环”这个需求依然存在于调试器、性能分析工具和对象序列化框架中。你都可以用快慢指针的思想做一次先导探测先判断是否有循环引用再决定要不要进入深度遍历。6.2 伪随机数与状态机检测另一个经典场景是检测迭代式函数的循环周期。比如一个随机数生成器内部有状态 S下一状态由某个函数 f 生成S f(S)。如果 f 的取值空间有限那么从任意状态出发最终必然会进入一个周期。用快慢指针可以快速判断这个周期是否存在以及周期长度是多少。这个思路在 Pollards Rho 算法里也有应用。那个算法用随机的迭代函数来找大数的因子如果迭代进入死循环算法就跑不出来。所以它沿用了龟兔赛跑的思想来检测循环。我第一次看到这种跨界应用时还挺惊讶的一道链表题的核心思想居然能用到数论领域。6.3 工程上的“预防式护栏”意识真实工程里很多链表、队列、缓冲池的实现都允许外部传入指针。你没法百分之百保证调用方不会制造出一个环。所以有些严谨的代码会在遍历链表的工具函数里加一个防护要么限制最大遍历步数要么使用快慢指针先做一次安全检查。我自己的习惯是在写任何“沿着 next 一直走”的循环时都会多问一句这个结构会不会有环如果来源不可控我一定会加护栏。这个意识不是从文档里学来的而是被线上问题教育出来的。第 141 题教会我的不只是两个指针怎么跑而是一种面对未知数据结构的防御性编程态度。6.4 变种题相交链表也能转换过来判环技巧还能延伸到一个经典变种题判断两个链表是否相交。有一个思路是把链表 A 的尾部接到链表 B 的头部然后对 B 做判环检测。如果 B 成环说明 A 和 B 原本就有交点再用 5.2 节的找入口方法入口就是它们的第一个相交节点。最后记得把 A 的尾部恢复原状。这种方式虽然不是这类题的最优解但展示了你对判环算法的迁移能力。面试时能主动讲出这种变换是很加分的。7. 复盘我在刷这道题时真正学到的东西7.1 题目之外的思维方式刷完这道题我最大的收获不是记住了快慢指针的代码而是建立了一个思维模型当遍历可能无限进行时先问“这个结构会不会有环”。这种思维在排查 bug 时特别有用。看到一段代码里有while (node) { node node.next; }这种结构我会下意识去查它的每个分支是否可能形成环。哪怕最后没有环这种警觉也能让你更快定位问题而不是等到服务器 CPU 飙升才发现不对。7.2 给不同基础的人的建议如果你是刚开始刷链表题的新手我建议先亲手写一遍哈希表法理解“节点对象本身才是可靠标识”这一概念然后立刻改写快慢指针法。不要只抄代码把 3.2 节的证明自己推一遍推完再去看入口算法理解会完全不同。如果你已经有一定基础重点放在两个地方一是把“为什么步长选 2”讲得有理有据二是把“相遇后怎么找入口”的推导写熟练。这两点正是面试中区分“背题选手”和“理解选手”的关键。7.3 一页纸刷题卡片我给你总结了一张可以直接抄进笔记的卡片方便以后快速复习项目内容问题判断链表是否有环基础解哈希表记录节点空间 O(n)最优解快慢指针空间 O(1)核心条件while fast and fast.next关键判断slow fast时返回 true入口问题相遇后一个指针回 head二者同速走到再次相遇易错点空链表、单节点、自环、指针判空顺序工程启示遍历不可信来源的链表时先想到是否成环这张卡片不需要背多看几遍自然就记住了。7.4 个人体感最深的教训最后分享一个我自己的体感。以前总觉得“判环”是一个很偏门的算法直到我参与维护一个缓存模块里面有一张复杂的双向链表。某个版本上线后偶尔出现请求卡住超时查了很久才发现是一个节点的 prev 指针被异常改写导致遍历时回到了之前的节点形成了一个不可见的环。那次排查之后我在所有遍历链表的代码里都养成了一个习惯先问构造来源再决定是否加步数护栏。这个习惯就是第 141 题真正留给我的东西。 
长河君 · 2026/10/16 5:44:02 · 阅读 1.2k 环形链表检测：从哈希表到快慢指针的算法解析
先讲一个我实际遇到过的情况。有次做模拟笔试我写了一个链表反转手写样例全过提交上去直接超时。当时完全懵后来把链表演算了一遍才发现测试数据里某个节点的 next 指回了之前的节点整个链表成了环。程序在 while 循环里出不来跑多久都是超时。碰过头之后我才真正重视这类题第141题“环形链表”问的就是这件事给定链表的头节点判断链表中是否存在环。这道题在题库里属于“看着简单、坑却不少”的代表。它考的不只是你会不会写两个解法还考察你对边界条件的敏感度、空间复杂度的取舍以及对一个经典算法思想——快慢指针也叫龟兔赛跑——的理解深度。这篇文章我从题面拆解开始把哈希表法和快慢指针法都过一遍包括相遇证明、常用陷阱、面试追问变形以及判环思想在真实系统里的应用。不管你是刚开始刷链表题的新手还是准备面试想查漏补缺的老手都能在这里找到可以直接拿去用的结论。1. 题面拆解判断链表成环到底在考什么1.1 题面描述与隐含信息原题的描述很简短给出一个链表的头节点 head判断该链表中是否有环。返回一个布尔值即可。但这里有一个容易让新手困惑的点题目描述里往往会提到一个 pos 参数表示尾节点 next 指针指向的节点索引从 0 开始如果 pos -1 则表示无环。很多人在提交代码时会下意识去找这个 pos 传进来结果发现函数签名里根本没有这个参数。原因很简单pos 只是题目在可视化环境里用来构造测试链表的参数不需要也不应该出现在你的解法函数里。你要做的只是拿到一个已经是“既成事实”的链表去判断它到底成环没有。要理解“环”的本质可以把链表想象成一张单向通行图。每个节点只有一条出边也就是 next。如果某个节点的 next 指向了自己或者指向了它前面的某个节点你就永远无法沿着 next 走到 null。此时链表不再是“链”而是一个带尾巴的圈。常见的三种测试形态需要心里有数普通链表每个节点最终指向 null无环。尾部接回中间节点这是最典型的环比如 1-2-3-4-2。自环一个节点的 next 指向它自己环长为 1。第三种情况最容易在代码里翻车。如果你写的循环条件是while (node ! null) node node.next;且不记步数遇到自环直接死循环。判环算法本质上就是要在不牺牲这种遍历能力的前提下把死循环变成可判定的逻辑。1.2 边界情况越简单越容易翻车很多时候一个解法本身不难难的是边界条件。这道题的边界集中在三种情况head 为空。只有一个节点且 next 指向 null。只有一个节点且 next 指向自己。我把这三种情况列成一张表方便你对照检查自己的代码输入形态是否有环快慢指针能否检测head null否能循环条件直接不满足返回 false单节点1 - null否能fast 走到 null返回 false单节点1 - 1是能快慢指针会相遇多节点尾部指回中间是能慢指针入环后必被追上从表格能看出一个健壮的解法必须显式处理空链表。否则你会在fast.next上直接读到空指针异常。这个细节是面试中最常见的减分项。1.3 为什么这道题是高频题环形链表在面试里高频出现原因不是它知识点有多深而是它特别适合考察“算法思维分层”。第一层能不能想到用哈希表记录遍历过的节点第二层能不能把空间压缩到 O(1)第三层能不能把快慢指针的相遇原理讲清楚并延伸到找环入口。更重要的是这个题是后续一堆链表问题的地基。比如环形链表 II 要求返回环的入口节点相交链表可以用判环思路间接求解还有一类“判断链表中是否存在无限循环”的系统级问题本质也是同一套思想。你把 141 吃透了后面那些题会轻松很多。2. 哈希表方案最直觉的解法为什么只是及格分2.1 核心思路与实现代码最直观的想法遍历链表每经过一个节点就把它记下来。如果后面某个节点已经出现过了就说明这条路走回了之前的地方链表成环。这里有一个关键点记录的是节点本身而不是节点的值。我之前见过有人用setint存节点的 value这是错的。环形链表题里不同节点的值可以完全相同比如 1-2-3-2-3 这种用值判断会误判而节点对象本身在内存里有唯一的地址用它作为 key 才是可靠的。Python 参考实现def hasCycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return FalseC 参考实现class Solution { public: bool hasCycle(ListNode *head) { unordered_setListNode* seen; ListNode* cur head; while (cur) { if (seen.count(cur)) return true; seen.insert(cur); cur cur-next; } return false; } };unordered_setListNode*存的是指针也就是节点的内存地址。只要同一个节点被二次访问地址必然相同判断准确。2.2 为什么面试官不会止步于这个答案哈希表法能跑过绝大多数在线评测时间复杂度和空间复杂度分别是 O(n) 和 O(n)。如果你面试时直接给出这个解法面试官通常会点头然后追问一句“能不能把空间复杂度降到 O(1)”被这么问不丢人因为 O(n) 空间的方案存在的意义主要是给思路做铺垫。在真实系统里链表可能非常长几百万个节点并不稀奇。如果每次判断成环都要开一个等规模的哈希表内存开销不可接受。更典型的是你需要判断的链表可能本身就在一个内存紧张的环境里比如嵌入式设备或者某个被压到极限的服务进程。这时候 O(1) 空间不是优化而是硬性要求。另外哈希表方案还有一个隐含陋习它“记住一切”。判环其实只需要判断“是否回到已经走过的节点”并不需要知道所有走过的节点。当你意识到这一点就会自然地思考有没有一种方式只用两个指针不记账也能判断2.3 空间权衡的实战意义我在写工程代码时对空间复杂度的敏感度比刷题时更高。哈希表法在 LeetCode 这类环境里很舒服因为测试用例规模有限。但你要是在一个高并发服务里给每个请求都开一个unordered_set去检测一个可能几百万节点的链表GC 压力和内存峰值都会让你很难受。所以我的建议是哈希表法可以作为“解释为什么需要优化”的引子但最终实现应该落到快慢指针上。面试时如果时间充足最好先把哈希表思路说一遍再过渡到 O(1) 空间解法这样能展示出你的复杂度意识。3. 快慢指针Floyd 判圈从直觉到严格证明3.1 龟兔赛跑的思想快慢指针的昵称叫龟兔赛跑。你让两个指针同时出发慢指针乌龟每次走一步快指针兔子每次走两步。如果链表没有环快指针会先一步到达终点 null如果链表有环快指针会在环里一圈圈地跑最终在某个节点追上慢指针。这个思想听起来像脑筋急转弯其实它对应的是一个成体系的判圈算法。算法的名字可能因人而异但核心逻辑很统一两个不同速度的指针在同一个结构上运动如果结构存在循环快的那个必然撞见慢的那个。为什么是“必然”直觉上环是一个封闭赛道兔子比乌龟快那么兔子总会追上乌龟。但如果你真的去实现会发现有一些微妙的前提条件需要证明才能放心使用。3.2 证明为什么两个指针一定相遇设从 head 到环入口的步数为 a环内节点数为 L。让慢指针和快指针同时从 head 出发慢指针速度为 1快指针速度为 2。慢指针到达环入口时一共走了 a 步。此时快指针已经走了 2a 步其中在环内已经转了 a 步。也就是说快指针在环内的位置相当于从入口前进 a 步的位置。对它当前相对入口的距离取模就是 a mod L。如果 a mod L 0说明快指针正好也在入口两个指针在这一刻就已经相遇检测结束。否则设 d a mod L快指针在慢指针前方 d 步的位置。沿着前进方向看快指针和慢指针之间的“追赶距离”是 L - d。接下来每一轮循环慢指针前进 1快指针前进 2两者的距离差减少 1。因为追赶距离 L - d 是一个小于 L 的正整数所以最多经过 L - 1 轮快指针就能追上慢指针。这个结论非常关键慢指针在环内不需要走满一整圈就会被追到。所以总循环次数大约是 a 加上不超过 L 的追赶步数即 O(a L)而 a L 不会超过链表总节点数 n 的量级。这就是为什么快慢指针判环的时间复杂度可以被证明为 O(n)并且不会出现无限循环。3.3 三种语言实现最常见的写法让 fast 初始也指向 headdef hasCycle(head): if not head: return False slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False注意这段代码在移动指针之后才比较所以不会出现“初始时 slow fast 导致误判”的问题。C 版本class Solution { public: bool hasCycle(ListNode *head) { if (!head || !head-next) return false; ListNode* slow head; ListNode* fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) return true; } return false; } };这里我先检查head和head-next避免后续对空指针解引用。实际上不写if (!head-next)也能运行因为while (fast fast-next)会兜底但显式处理更容易读。Java 版本public boolean hasCycle(ListNode head) { if (head null) return false; ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) return true; } return false; }三种语言的逻辑完全一致只是语法糖不同。核心就是一句fast每走两步slow走一步相遇即返回 true。4. 快慢指针的边界条件最容易白给的三个坑4.1 快指针从 head 走还是从 head.next 走网上很多代码会让 fast 初始化为head.next而慢指针初始化为 head。这样写本身没问题但会带来一个连锁反应循环条件里必须更早地判断fast和fast.next是否为空。我见过不少初学者把fast head和while (fast fast.next)组合错也见过把fast head.next和while (slow ! fast)组合错结果要么空指针要么死循环。我的建议很简单统一用fast head的初始化。这样 while 循环条件写起来最自然只要fast和fast.next都非空就继续走。判断顺序记住一条先判断fast本身再判断fast.next因为后者依赖前者存在。两种初始化对比初始化方式循环写法注意点slow head; fast headwhile (fast fast.next)移动后再比较最推荐slow head; fast head.nextwhile (slow ! fast)循环内要判空容易漏如果你选择第二种循环里必须在移动前检查fast和fast.next是否为空否则访问fast.next.next会直接崩溃。相比之下第一种写法更优雅也不易出错。4.2 步长选 2 还是选 3有人会问快指针一次走三步行不行答案是行但在面试里不建议。原因有三个。第一步长为 2 时快指针相对慢指针的速度差正好是 1。这意味着每一轮循环两个指针之间的距离稳定缩短 1 步绝对不会“跳过去”导致思想上的纠结。虽然数学上步长为 3 也能追上但证明时要处理相对速度差为 2 的情况追及轮次可能更多边界条件也更脆。第二步长越大快指针越容易提前碰到 null。在无环链表上步长 2 已经让快指针承担了提前结束的任务步长 3 会让这种“提前触底”在代码里更难预判。第三面试官真正想听的往往不是一个更花哨的步长而是你能解释清楚步长 2 的工程折中速度差最小逻辑最简单数学证明最直观。你如果能说出“2 是相对速度等于 1 的最小步长”面试官会觉得你对细节是真懂。4.3 终止条件循环判空的正确写法这道题最容易的翻车点不是理解错而是空指针异常。常见的错误版本长这样while fast.next and fast.next.next:如果fast本身是 None你连fast.next都访问不了。所以正确顺序一定是while fast and fast.next:先保证fast存在再访问它的 next。同理fast fast.next.next这行代码只有在fast.next非空时才安全。把它放在 while 条件里已经保证了就不会出错。再补充一个实际测试时很有用的技巧如果你手头有个可能成环的链表又不想写完整判环代码可以先在循环里加一个计数器最多走 n 步就退出。这种“预防式护栏”在真实 debug 里非常管用哪怕最后定位到的问题不是环也至少能避免把开发环境跑挂。4.4 自环的特殊情况自环是head.next head。这种情况下两个指针都从 head 出发第一次移动后 slow head.next也就是 headfast head.next.next也是 head两者相等返回 true。逻辑没问题。但我见过有人在这种形态上栽跟头原因是用了哈希表解法却记录了“节点的值”。如果 head 的值恰好和后续某个节点值相同就会误判为有环。所以我再强调一遍哈希表务必存节点对象或指针不要存值。5. 面试追问从“有没有环”升级到“环的入口在哪”5.1 环形链表 II 的考法第 141 题只要求返回布尔值但面试官通常会接着问如果链表有环请返回环的入口节点如果没有环返回 null。这就是环形链表 II 的考法。先想一个简单但算出错的方法用哈希表遍历时第一个重复遇到的节点就是入口。因为当你第二次经过某个节点时它就是环的起点。这个解法正确但空间复杂度是 O(n)。面试官大概率会要求你继续优化到 O(1)。5.2 相遇点与入口的关系推导要找到入口得把前面证明里的式子再推进一步。设慢指针从 head 走到相遇点总步数记为 a x其中 a 是 head 到环入口的步数x 是慢指针从入口进入环后到相遇点之间走的步数。因为快指针速度是慢指针的两倍所以快指针总步数是 2(a x)。两指针步数差为 a x而这个差值正好是快指针在环内比慢指针多绕的圈数记为 kL。于是得到a x kL这个等式是找入口的钥匙。把它改写成 a kL - x。这个式子的几何含义是从相遇点继续往前走 a 步你会恰好回到环入口。因为 kL - x 相当于绕了 k 圈后再倒退 x 步而倒退 x 步正是从相遇点回到入口的距离。所以解法是在第一次相遇后把一个指针重新放回 head另一个留在相遇点。两个指针都改成一次走一步。当 head 出发的指针走过 a 步到达入口时相遇点的指针同样走了 a 步正好也停在入口。两者再次相遇的位置就是环入口。代码实现def detectCycle(head): fast slow head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: slow head while slow is not fast: slow slow.next fast fast.next return slow return None这个解法的空间复杂度仍然是 O(1)时间还是 O(n)。你在面试里如果能把这个推导过程完整讲出来含金量比背十道题都高。5.3 顺带说说“环的长度”找到入口之后环的长度就很好算了从入口出发沿着 next 一直走再次回到入口时的步数就是环长 L。这个操作也需要一个计数变量并且注意要先移动再计数避免上来就把入口算成 0。如果你不知道入口只知道相遇点也可以数环长从相遇点出发继续一路 next回到相遇点时的步数同样是 L。因为在环内任意节点作为起点走一圈回到自身的步数都是 L。面试官还可能在追问里问“能不能在一次遍历同时求出环长和入口”这个通常不需要你现场实现把思路讲清楚就行先用快慢指针判环并得到相遇点再走一圈数出环长最后用 5.2 的双指针法找入口。每一步的复杂度加起来依然是线性的。6. 判环思想在真实系统里的用武之地6.1 对象图与循环引用检测我最早觉得判环算法只能用来做题后来维护老项目时才发现它在真实系统里的用处比想象中大得多。比如某些语言在垃圾回收时需要对对象图做可达性分析。对象之间的引用如果形成了环一个简单的递归遍历就会无限递归。虽然现代回收器会用三色标记等手段避免无限循环但“检测对象图是否有环”这个需求依然存在于调试器、性能分析工具和对象序列化框架中。你都可以用快慢指针的思想做一次先导探测先判断是否有循环引用再决定要不要进入深度遍历。6.2 伪随机数与状态机检测另一个经典场景是检测迭代式函数的循环周期。比如一个随机数生成器内部有状态 S下一状态由某个函数 f 生成S f(S)。如果 f 的取值空间有限那么从任意状态出发最终必然会进入一个周期。用快慢指针可以快速判断这个周期是否存在以及周期长度是多少。这个思路在 Pollards Rho 算法里也有应用。那个算法用随机的迭代函数来找大数的因子如果迭代进入死循环算法就跑不出来。所以它沿用了龟兔赛跑的思想来检测循环。我第一次看到这种跨界应用时还挺惊讶的一道链表题的核心思想居然能用到数论领域。6.3 工程上的“预防式护栏”意识真实工程里很多链表、队列、缓冲池的实现都允许外部传入指针。你没法百分之百保证调用方不会制造出一个环。所以有些严谨的代码会在遍历链表的工具函数里加一个防护要么限制最大遍历步数要么使用快慢指针先做一次安全检查。我自己的习惯是在写任何“沿着 next 一直走”的循环时都会多问一句这个结构会不会有环如果来源不可控我一定会加护栏。这个意识不是从文档里学来的而是被线上问题教育出来的。第 141 题教会我的不只是两个指针怎么跑而是一种面对未知数据结构的防御性编程态度。6.4 变种题相交链表也能转换过来判环技巧还能延伸到一个经典变种题判断两个链表是否相交。有一个思路是把链表 A 的尾部接到链表 B 的头部然后对 B 做判环检测。如果 B 成环说明 A 和 B 原本就有交点再用 5.2 节的找入口方法入口就是它们的第一个相交节点。最后记得把 A 的尾部恢复原状。这种方式虽然不是这类题的最优解但展示了你对判环算法的迁移能力。面试时能主动讲出这种变换是很加分的。7. 复盘我在刷这道题时真正学到的东西7.1 题目之外的思维方式刷完这道题我最大的收获不是记住了快慢指针的代码而是建立了一个思维模型当遍历可能无限进行时先问“这个结构会不会有环”。这种思维在排查 bug 时特别有用。看到一段代码里有while (node) { node node.next; }这种结构我会下意识去查它的每个分支是否可能形成环。哪怕最后没有环这种警觉也能让你更快定位问题而不是等到服务器 CPU 飙升才发现不对。7.2 给不同基础的人的建议如果你是刚开始刷链表题的新手我建议先亲手写一遍哈希表法理解“节点对象本身才是可靠标识”这一概念然后立刻改写快慢指针法。不要只抄代码把 3.2 节的证明自己推一遍推完再去看入口算法理解会完全不同。如果你已经有一定基础重点放在两个地方一是把“为什么步长选 2”讲得有理有据二是把“相遇后怎么找入口”的推导写熟练。这两点正是面试中区分“背题选手”和“理解选手”的关键。7.3 一页纸刷题卡片我给你总结了一张可以直接抄进笔记的卡片方便以后快速复习项目内容问题判断链表是否有环基础解哈希表记录节点空间 O(n)最优解快慢指针空间 O(1)核心条件while fast and fast.next关键判断slow fast时返回 true入口问题相遇后一个指针回 head二者同速走到再次相遇易错点空链表、单节点、自环、指针判空顺序工程启示遍历不可信来源的链表时先想到是否成环这张卡片不需要背多看几遍自然就记住了。7.4 个人体感最深的教训最后分享一个我自己的体感。以前总觉得“判环”是一个很偏门的算法直到我参与维护一个缓存模块里面有一张复杂的双向链表。某个版本上线后偶尔出现请求卡住超时查了很久才发现是一个节点的 prev 指针被异常改写导致遍历时回到了之前的节点形成了一个不可见的环。那次排查之后我在所有遍历链表的代码里都养成了一个习惯先问构造来源再决定是否加步数护栏。这个习惯就是第 141 题真正留给我的东西。