刷链表题的人基本绕不开“141. 环形链表”这道题。它在面试里出现频率极高不是因为它难而是因为它足够经典一个思路把“遍历链表”和“检测循环”结合到一起用最简单的代码解决一个让人头疼的问题。题目本身只是判断链表里有没有环但延伸出来的快慢指针思想几乎成了后续一堆题目的基石。我第一次做这道题的时候用的是哈希表思路很直白边走边记记到重复节点就说明有环。后来在面试里被追问“能不能不用额外空间”才认真把快慢指针搞透彻。这篇文章会把两种解法、快慢指针背后的数学原理、从读题到 AC 的完整过程以及我踩过的坑全部摊开讲。适合刚接触链表的人也适合刷题刷到一定阶段、想把原理补齐的人。1. 题目拆解先搞清楚到底在问什么1.1 输入输出与边界条件题目给出一个单链表的头节点head让你判断链表中是否存在环。所谓“环”就是链表的某个节点的next指针指向了它之前已经出现过的某个节点导致遍历永远走不到尾。这里有几个必须想清楚的边界情况空链表也就是head为null不可能有环直接返回false只有一个节点且next指向自己这是环返回true只有一个节点但next为null不是环。很多人在写代码时只考虑了“环存在”和“环不存在”两种正向场景忽略了单节点自环这种特殊情况。自环在构造测试用例时很常见一旦代码里没有对head.next的判空很可能在快指针移动时直接抛出空指针异常。1.2 这个题想考察的能力力扣给这个问题打上的标签是“哈希表”和“链表”。但从面试官的角度来看这道题真正考察的是两个层次的能力第一层能不能想到用哈希表记录遍历过的节点。这是大部分人第一反应能想到的方案思路简单实现容易但空间复杂度是 O(n)。第二层能不能在提示“不用额外空间”之后想到快慢指针。这考察的是对链表遍历规律的理解在有环的情况下两个速度不同的指针只要不停移动最终必然相遇。这个结论听起来简单真正理解它为什么成立的人却不多。所以这道题不是单纯考“会不会写代码”而是考你能不能把“遍历”升级为“用相对速度判断循环”并且敢不敢在代码里写出一个看起来可能无限循环的while结构。2. 方案一哈希表记录访问过的节点2.1 为什么第一反应会想到哈希表从人类的直观思维出发“判断链表里有没有重复出现的节点”最自然的做法就是拿一个本子把见过的节点都记下来。每到一个新节点先翻翻本子发现记过就说明绕回来了没记过就写上去继续走。用哈希表实现这个“本子”是因为哈希表的插入和查找平均都是 O(1) 时间遍历一遍链表总时间复杂度为 O(n)。判断两个节点是否相同比较的是节点的引用地址而不是节点里的val值这一点很多人都容易搞混。2.2 代码实现与细节我用 Java 和 Python 各写一版方便不同语言背景的人直接对照。public boolean hasCycle(ListNode head) { SetListNode seen new HashSet(); ListNode cur head; while (cur ! null) { if (!seen.add(cur)) { return true; } cur cur.next; } return false; }def hasCycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return FalseJava 版本里seen.add(cur)这个方法非常关键。它的返回值是布尔值如果集合里已经存在这个元素返回false同时不会重复插入如果不存在返回true并插入。利用这个特性可以少写一次contains判断代码更简洁。Python 版本要注意的是cur in seen判断。Python 的set对自定义对象的哈希默认基于对象的内存地址所以同一个节点对象被重复访问时一定能被识别出来。2.3 这个方案的优点和软肋优点是直观、不易出错。哪怕你完全不理解快慢指针只要知道哈希表的基本用法就能把这道题写出来。对于刚接触数据结构的人来说这是一个很好的“保底方案”。软肋也很明显空间复杂度 O(n)。在链表节点特别多的时候哈希表会额外占用一块不小的内存。如果题目要求空间复杂度 O(1)这个方案就不合格了。我在实际调试中还发现一个容易被忽略的问题哈希表判断的依据是节点引用不是节点值。如果你构造测试用例时创建了两个val相同但地址不同的节点它们不算同一个节点哈希表不会认为链表有环。很多初学者在这里犯迷糊以为值相等就是环这完全是误解。3. 方案二快慢指针空间换时间的反义词3.1 从“记路”到“追及”的思路转变哈希表方案的思路是“记住走过的路”而快慢指针方案的思路完全不同你不记路但你能感觉到自己在绕圈。想象你在操场上跑步跑道是环形的。你跑得慢别人跑得快。如果跑道是直的快的人只会越跑越远你们永远不会再相遇。但如果跑道是环形的快的人哪怕一开始领先很多最终也会从后面追上你甚至超过你之后再次相遇。链表的环就是这个环形跑道。落实到代码上维护两个指针slow每次走一步fast每次走两步。如果链表没有环fast会先到达末尾循环结束返回false如果链表有环slow和fast最终一定会指向同一个节点返回true。3.2 常见写法与关键判断条件先给出我比较推荐的一种写法public boolean hasCycle(ListNode head) { if (head null || head.next null) { return false; } 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; }这段代码里两个指针都从head出发。循环条件里的fast ! null fast.next ! null是安全保证缺一不可。如果fast本身是null说明走到链表末尾了如果fast.next是null说明fast是最后一个节点再跳两步就空指针了。另一种常见写法是把fast初始化为head.nextpublic 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; }这种写法把“先判断再移动”变成了“先比较再移动”。如果两个指针一开始就相等说明链表是空表或单节点但前面已经做了边界处理所以这里不会有问题。3.3 手写代码时最容易翻车的5个地方第一忘记对head判空。head null时进入循环执行head.next直接空指针。第二循环条件只写fast ! null漏掉fast.next ! null。当fast恰好是链表的最后一个节点时执行fast.next.next仍然会空指针。第三把slow fast的判断放在指针移动之前。初始状态下两个指针都指向head如果先判断就会直接返回true结果完全错误。必须先移动再判断。第四用slow.next和fast.next.next时没有考虑slow.next是否为null。不过只要fast的判空条件正确slow就不会走到null因为slow的速度是fast的一半fast都还没到末尾slow更不可能到。第五循环次数没有上限心里没底。很多人在写while (true)时犹豫怕死循环。其实只要链表有环快慢指针必相遇循环必然退出如果链表无环判空条件会退出循环。这个看似“无限”的循环实际上是有限步的。4. 快慢指针的数学原理为什么走两步能相遇4.1 相遇的本质是追及问题如果要给面试官讲清楚快慢指针为什么有效不能只说“跑得快的人会追上跑得慢的人”你得能推出来。设链表无环部分的长度为a环的长度为b。假设slow和fast都从head出发slow每次走 1 步fast每次走 2 步。当slow走完无环部分到达环的入口时它走了a步。此时fast已经走了2a步其中a步在无环部分剩下的a步在环里。关键在这里fast在环里的位置是“从环入口开始又往前走了a mod b步”。此时slow刚到环入口与fast相距多少如果a mod b 0说明fast恰好也在这个环入口处两人直接相遇。一般情况下假设环入口到fast当前位置的距离是a mod b那么fast追slow需要补上的距离是b - (a mod b)当a mod b ! 0时。因为slow进入环之后每移动一轮fast相对slow前进 1 步所以经过b - (a mod b)轮之后两者必然相遇。这个推导说明了一个结论无论无环部分的长度是多少无论环有多长只要环存在快慢指针必相遇而且是有限步内相遇。4.2 为什么不建议快指针走三步看代码的时候很多人会冒出疑问既然fast走两步能相遇走三步是不是更快结论是不能随便换走三步会有数学上的风险。设fast每次走k步slow每次走 1 步则两者的相对速度是k - 1。问题变成在模b的意义下快指针能否通过“每轮减少k-1步”的方式精确到达慢指针的位置。如果b和初始相对距离的组合导致每一步相对位置变化永远跳过目标位置就可能永远无法精确重合。举个例子环长b 4初始距离差为 1k 3相对速度是 2。每轮之后距离差变为1 - 2 -1也就是 3再下一轮又变回 1。快指针永远在 1 和 3 之间横跳永远精确踩不到 0。虽然实际循环中的“相遇”是在某个节点上指针重合但在这种组合下两者确实永远不会指向同一个节点。步长差为 1也就是k 2是最安全的选择不管环长多少每一轮都精确追近一格不会跳过去。这也是业界标准做法。4.3 步长与环长度的关系再严谨一点当快指针走 2 步、慢指针走 1 步时相对速度为 1等价于每一轮两者之间的距离减 1所以追及步数是一个整数必然能减到 0。这就是“走两步”的不可替代性。从复杂度上看slow进入环之前两者都在无环部分移动耗时 O(a)slow进入环后最多再走不到一圈的距离耗时 O(b)。合起来是 O(a b)也就是 O(n)。空间上只用两个指针O(1)。这个复杂度是哈希表方案做不到的。5. 完整实操从读题到 AC 的思考过程5.1 先写测试用例再写代码很多刷题的人习惯上来就写代码我觉得这道题更好的顺序是先构造测试用例。因为“链表有环”本身不是一个能直接写在代码里的输入你需要自己构造一个带环的链表这能帮你提前理解题目的数据结构。构造带环链表的过程很简单准备四个节点按顺序连接然后把最后一个节点的next指向第二个节点形成一个环。ListNode node1 new ListNode(1); ListNode node2 new ListNode(2); ListNode node3 new ListNode(3); ListNode node4 new ListNode(4); node1.next node2; node2.next node3; node3.next node4; node4.next node2; // 形成环然后分别测试三种情况hasCycle(node1)返回true把node4.next改为null再调用返回falsehasCycle(null)返回false。这三种用例覆盖了核心路径代码写完后能直接验证。5.2 构造自环与长链环的调试手段自环很隐蔽node.next node只有一个节点但形成了环。很多代码在判断head.next null时会把自环误判成无环。这个边界必须在代码里显式处理。在调试时如果你怀疑自己的代码在某个链表上进入了死循环可以在代码里临时加一个计数器比如运行超过 10000 次就打印节点值并退出。这种方法能快速定位“到底是没判空导致空指针还是逻辑错误导致死循环”。还可以在快慢指针移动的每一轮打印slow.val和fast.val对比它们的轨迹。在一个 1 到 4 的环里slow的轨迹是 1、2、3、4、2、3、4……fast的轨迹是 1、3、2、4、3、2……你能直观看到它们什么时候重合。5.3 一次完整的实操心路我在本地跑这道题的时候第一版用的是哈希表测试用例秒过但我不满足开始尝试快慢指针。第一次写的时候我犯了“先判断相等再移动指针”的错误导致单节点链表直接返回true。后来把slow fast的判断移到移动之后才通过。接着我试了fast head.next的写法又遇到一个问题当链表只有一个节点时head.next是null我的边界条件head.next null已经拦截了这种情况所以没问题。但如果是两个节点的无环链表fast初始指向第二个节点slow指向第一个进入循环后slow走一步到第二个节点fast走两步变成null判空退出返回false结果也是对的。把这些组合都跑一遍之后我对这道题的信心才真正建立起来。写题和背题的区别就在这里你亲自踩过边界条件的坑才知道为什么每一条判空都必不可少。6. 常见问题与排查技巧实录6.1 常见错误清单错误现象根本原因解决办法空指针异常没有判断head或head.next为 null开头显式处理空表和单节点单节点链表返回 true判断相等放在移动之前先移动再判断无环链表死循环循环条件里只判断fast ! null漏掉fast.next ! null两个判空条件都写上值相等误以为节点相等混淆节点引用和节点值始终比较对象引用快慢指针永远不相遇快指针步长设置过大固定快指针每次走两步这张表里最值得警惕的是第一行和第三行本质上都是在访问null.next但出现的时机不同。head为空是初始状态问题fast.next为空是遍历过程中的问题两者都要防。6.2 关于复杂度和扩展性的思考哈希表方案的时间复杂度是 O(n)空间复杂度是 O(n)。快慢指针方案的时间复杂度是 O(n)空间复杂度是 O(1)。在面试时面试官通常会先认可哈希表方案然后追问“能不能优化空间”这时候你再给出快慢指针整个回答过程会显得思路清晰、层层递进。如果你想让答案更有含金量可以在讲完快慢指针后主动补充这道题可以继续延伸为“找到环的入口节点”也就是力扣第 142 题。思路是在判定有环后让slow回到headfast留在相遇点两者都以每次一步的速度前进再次相遇的位置就是环入口。这个结论可以用数学推导验证但现场能把思路讲清楚已经很加分。7. 同类型题目串讲一个思路吃透一类题7.1 从判断有没有环到找环入口力扣第 142 题“环形链表 II”是“141. 环形链表”的直接升级版。它不仅要判断有没有环还要返回环的入口节点。做法是先用快慢指针找到相遇点。设head到环入口的距离为a环入口到相遇点的距离为b相遇点继续走到环入口的距离为c。慢指针走的路程是a b快指针走的路程是a n(b c) b因为快指针速度是慢指针的两倍所以2(a b) a n(b c) b化简得a (n - 1)(b c) c。这个公式的实际意义是从head出发走到环入口的距离等于从相遇点出发绕 n-1 圈再走 c 的距离。所以让一个指针从head出发另一个从相遇点出发都每次走一步它们必然在环入口相遇。你不需要在面试中把每一步推导都背下来但一定要能说出“为什么再次相遇的节点就是入口”这个核心逻辑。7.2 快乐数同一个模板的变体力扣第 202 题“快乐数”看起来和链表毫无关系但它的本质也是环检测。数字按照各位平方和不断迭代有两种可能最终变成 1或者进入一个不包含 1 的循环。把每次计算得到的新数字想象成链表的节点如果一个数字之前出现过就说明进入循环了这就是环检测问题。用快慢指针一个每次算一次平方和另一个每次算两次平方和如果快指针遇到了慢指针且不是 1就说明进入了循环。我第一次发现这个对应关系的时候确实觉得这类题出得妙。7.3 一个思路的通用价值还有力扣第 287 题“寻找重复数”也可以用类似的抽象思路把数组元素值当作指针索引数组本身可以看成一个链表重复出现的值意味着环的存在。虽然这道题的最优解通常是二分或位运算但能一眼看出它和“环形链表”有关联本身就是一种能力的体现。回到“141. 环形链表”这道题本身它最值得学的不是那个while循环怎么写的而是“通过相对速度判断循环结构”这一抽象方法。你在一个领域里反复用过之后会在很多意想不到的地方遇到它。最后再分享一点实际体会刷这道题的时候我第一次见识到一个简单的数据结构能藏下这么多细节。哈希表方案一写就过快慢指针方案却让我反复吃瘪原因全部出在边界条件上。后来我把链表题的常见边界列成了一张检查清单空表、单节点、自环、双节点无环、尾部成环每次都对照一遍正确率提升非常明显。如果你也是刚接触到“环形链表”这道题我的建议是别急着去背代码。先拿纸笔模拟一遍快慢指针在 1 到 4 的环上的运动轨迹再自己写一版哈希表和一版快慢指针对比两者在空间上的差异。等你把“为什么走两步能相遇”彻底想通了这道题就真正属于你了。后面再做 142 题、202 题你会有一种“原来都是同一个套路”的感觉。