如果你在LeetCode上刷到第141题“环形链表”第一反应大概是这题有什么难的三行代码就能写完。可真正在面试里被这道题拦住的人从来不是写不出“判断有没有环”的代码而是被追问“为什么快慢指针一定会相遇”时哑口无言。我当年也一样AC了141题之后去刷题解区看得一愣一愣后来把142题“环形链表 II”也练透才发现这组题的精华根本不在判断而在数学推导。这一篇就把环形链表系列彻底讲透从141题的快慢指针模板到142题环入口的证明再到我刷题时踩过的坑和面试里怎么把推导讲清楚全部写给你。1. 这道题到底在考什么从题目表象到核心考点1.1 题目原文与基本印象LeetCode 141题“环形链表”的题目描述短到让人怀疑自己看错了给你一个链表的头节点head判断链表中是否有环。如果链表中存在某个节点可以通过连续跟踪next指针再次到达这个节点就说明链表中有环返回布尔值即可。官方难度标签是“简单”但它在面试中的出现频率却常年排在前列。在LeetCode题解区环形链表的题解一抓一大把高产博主们甚至能用好几篇长文把快慢指针讲出花来。之所以这么多人写是因为这题在算法面试里的出镜率实在太高而“简单”只是表象真正能答好的人并不多。表面上看这题只考察链表遍历沿着next一个个走如果走到null就说明链表有尽头没环如果一直走不出去就有环。但如果你真的只在代码里写了这么一个遍历循环你会发现一个问题怎么知道“一直走不出去”没有终点标志程序永远不会自己停下来。所以这道题真正的难点在于如何在有限步内判断一个可能无限循环的结构这才是它被归为经典题的原因。1.2 隐藏在“有环”背后的真实考点第一层考点是数据结构基本功链表节点的引用关系、指针移动、循环终止条件的控制。这一层大多数人都能过关毕竟链表遍历是入门操作。第二层考点是空间复杂度意识。判断有没有环最朴素的想法是用哈希表记录访问过的节点这个方案能通过测试但面试官紧接着就会问能不能把空间复杂度降到O(1)。这时候快慢指针的价值就体现出来了它只需要两个指针变量不需要任何额外容器。第三层才是真正的分水岭数学理解。如果你只知道快慢指针模板却说不出“为什么一定会相遇”面试官大概率会怀疑你是背的答案而不是自己推导出来的。这一层能拦住一大批人。所以我认为环形链表的真正考点不是代码而是Floyd判圈算法背后的数学。1.3 141和142的递进关系判断是热身定位才是正餐141题只问“有没有环”答案是布尔值142题“环形链表 II”则要求返回环的入口节点。判断存在与否很简单但定位入口需要你彻底理解环的结构链表头到入口的距离、环的周长、入口到相遇点的距离三者之间存在精确的数量关系。我把这组题比作看病141题相当于医生告诉你“体内有结石”142题则是要精确指出结石在哪个位置。前者靠仪器扫一遍就能定性后者需要建立完整的内部结构图。刷题时我强烈建议直接把142题当作重点因为只要142题的推导吃透了141题就是它顺手白送的小弟。2. 快慢指针的数学原理为什么两个指针一定会碰面2.1 先建立直觉操场上的追人游戏假设你和一个朋友在圆形跑道上跑步你跑得慢每秒1米他跑得快每秒2米。他从后面出发一开始可能离你有段距离但只要跑道是闭合的他一定能追上你。原因不用列公式也能想明白他相对你每秒逼近1米而跑道长度有限追完一圈内的距离就够了不可能永远追不上。链表的环就是这条环形跑道。慢指针每次走1步相当于每秒1米快指针每次走2步相当于每秒2米。只要链表里有环两个指针早晚在环上碰面。这个直觉是判断环形链表的核心。2.2 一步一步推相遇是有限步内的必然事件把直觉转成严谨推导其实只需要几行。假设慢指针刚进入环的那一刻慢指针在环入口快指针已经在环内的某个位置。设环的周长为L此时快指针与慢指针沿着环的前进方向距离为dd的取值范围是0到L-1。从这一刻开始每一轮迭代中慢指针前进1步快指针前进2步。于是每一轮过后快指针相对慢指针的净距离减少1。经过d轮这个距离减到0也就是两者相遇。因为d最大也就是L-1所以最多L-1轮后必定发生相遇。这里有个关键前提链表中确实存在环。如果链表没有环快指针会先走到null循环退出直接返回False根本不存在“追得上与否”的问题。实际上只要快指针每次比慢指针多走一步也就是速度差恒为1追及就必然发生快指针每次走2步是最经典的设置既保证追赶又不会因为步幅过大而跳过慢指针。提示为什么快指针不会“跳过去”错过慢指针因为快指针虽然一次走两步但它是连续经过两个节点的慢指针每次只走一个节点两者在节点上的到达是连续的不存在从慢指针头顶跨过去的瞬间。相当于快指针相对慢指针每轮只接近1个单位而不是每轮跳过1个节点。2.3 打破几个常见的想当然我在评论区见过不少误解挑三个最典型的说一说。误解一相遇时快指针一定比慢指针多走了一圈。真相是多走的圈数不是固定值。如果环的入口离链表头很远慢指针还没进入环时快指针可能已经在环里绕了好几圈如果环很大快指针也可能在追上时还没绕完一整圈。多走的圈数取决于链表头到环入口的距离、环周长和相遇位置三者共同决定。误解二相遇点一定在环入口处。真相是相遇点可以是环上任何一个位置。它取决于慢指针进入环的那一刻快指针所在的位置而这个位置受环外链表的长度影响。所以不要期待用相遇点直接判断入口那是下一层问题要解决的。误解三快慢指针只知道“有没有环”无法更进一步。这个误解最容易拖慢进步。实际上Floyd判圈算法最大的亮点是第一次相遇后可以继续推导出环入口的位置这正是142题的做法。3. 判断有环的代码实现与边界处理3.1 141题最简实现快慢指针版我先把代码放上来再逐行解释为什么这么写。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def hasCycle(head: ListNode) - bool: slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False这段代码有几个值得注意的设计点。循环条件写成while fast and fast.next而不是while fast是因为快指针每次要走两步。如果当前节点是None说明链表为空或已走到尾部如果当前节点的next是None说明下一步快指针会走到None再在循环体里执行fast.next.next就会抛空引用异常。把这两个条件都挡在循环外面是最稳妥的写法。比较用slow is fast而不是slow.val fast.val是因为环的判断关注的是“同一个节点对象”而不是值相同。链表中完全可能有两个不同的节点携带相同数值值比较会造成误判。我见过有人用slow fast在Python的ListNode默认比较逻辑下这可能退化为值比较一旦遇到重复值就出假阳性。从时间复杂度看快指针最多遍历一遍非环部分进入环后最多再走L-1轮就能追到慢指针所以总时间复杂度是O(N)空间复杂度O(1)。这已经是这类题的最优解。3.2 哈希表解法作为过渡方案也要能写出来虽然快慢指针是最终答案但了解哈希表方案仍然有用因为它是最直白的思路。def hasCycle(head: ListNode) - bool: seen set() while head: if head in seen: return True seen.add(head) head head.next return False这个办法的本质是给每个访问过的节点留痕。一个节点如果在哈希表里出现两次说明遍历过程中走回到了已经走过的节点自然存在环。直观且不易出错对新手相当友好。但它的代价是额外空间。每遍历一个新节点set里就要存一个引用最坏情况下节点数N个空间复杂度O(N)。快慢指针则只需要两个引用变量空间复杂度O(1)。两者在时间复杂度上都是O(N)差距集中在空间上。实战中处理几十万节点的链表O(N)的set不是不能用但面试要考察的恰恰是你有没有意识到并优化掉这个代价。方案时间复杂度空间复杂度是否修改链表哈希表O(N)O(N)否快慢指针O(N)O(1)否面试时我的建议是先说哈希表再说“但空间可以优化到O(1)”然后引出快慢指针。这比直接甩快慢指针显得更有思考过程也符合面试官想听“从朴素到优化”的期待。3.3 空链表、单节点、尾节点自环边界case逐个过刷题最怕的是测试用例故意恶心你。我总结了几类绕不开的边界case你可以直接拿来测自己的实现空链表head为None直接返回False。单节点链表节点next为None返回False。单节点自环唯一节点的next指向自己返回True。双节点环1-2-1第二个节点指回头节点返回True。长直链加小环比如100个节点的直线部分接一个3节点的环。快慢指针写法的好处是这些边界几乎不需要特殊判断统一的循环条件能覆盖掉。单节点自环时fast从head出发循环条件检查fast and fast.next成立因为fast非空且fast.next指向自身非空slow走一步还在原节点fast走两步也回到原节点is比较成立返回True。这个case最能验证你对环的理解到不到位。4. 进阶找到环入口的数学推导与142题实现4.1 给路径命名头到入口、入口到相遇点、相遇点绕回入口在做142题之前先把推导需要的三个距离定义清楚。我不画图直接用文字描述a链表头到环入口的距离。b从环入口出发沿着链表的next方向走到快慢指针第一次相遇点的距离。c从相遇点继续沿着next方向绕回到环入口的距离。L环的周长显然L b c。第一次相遇时慢指针走过的总路程是a b。快指针走过的总路程是a b nL其中n是快指针在环内比慢指针多绕的整圈数n至少为1。这个“至少为1”可以这样理解fast速度是slow的两倍在slow进入环之前fast已经在环中走动当两者在环上同一位置相遇时fast比slow多跑的路程必然是整个环长的整数倍。后面你会发现n具体是多少根本不重要。4.2 核心等式怎么来的a (n-1)L c的完整推演因为fast的速度是slow的两倍相同时间内的路程也是两倍所以有2(a b) a b nL移项合并立刻得到a b nL再代入L b c用b和c消去ba nL - b n(b c) - b (n - 1)L c这就是那个关键等式a (n - 1)L c。这个等式的含义是从链表头走到环入口需要的步数a恰好等于从相遇点沿着环绕(n-1)整圈再走c步到达入口的距离。也就是说只要有一个指针从head出发一次走一步同时让另一个指针从相遇点也一次走一步它们必然在环入口处第二次相遇。理解这个推导比背下代码重要一百倍。因为面试官一旦追问“为什么第二步两个指针要同速走”你就能直接背出这五行式子而不是支支吾吾。注意很多资料把这个推导简化成“从相遇点到入口的距离等于从head到入口的距离”严格来说不够准确应该是“从相遇点绕环若干整圈再走c步到入口的距离”等于a。口头上简化可以心里要清楚等式里还有一个整数圈的项。4.3 142题完整代码与一个具体例子的手算模拟有了等式之后实现就非常简单def detectCycle(head: ListNode) - ListNode: slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: # 第一次相遇后新指针从头部出发slow从相遇点出发 ptr head while ptr is not slow: ptr ptr.next slow slow.next return ptr return None我拿一个比较有代表性的例子手动走一遍。构造链表1 - 2 - 3 - 4 - 5其中节点5的next指向节点3也就是环入口在3环长L 3即3-4-5-3链表头到入口距离a 2。快慢指针从head出发第一轮后slow在2fast在3。第二轮后slow在3fast在5。第三轮后slow在4fast在4二者相遇于节点4。此时b 1c 2n 1验证a (n-1)L c 0 2 2成立。第二步ptr从head节点1出发slow从节点4出发都一次走一步ptr到节点2slow到节点5。ptr到节点3slow到节点3。ptr is slow判定成立返回节点3这正是环入口。这个例子环小看着几乎是一眼看出答案换成环外部分几十个节点的大链表流程完全一致只是需要多走几十步而已。142题整体的时间复杂度仍然O(N)空间复杂度O(1)因为两个阶段的总步数都不超过节点总数。5. 我的刷题经验从理解到能讲清楚面试5.1 高频踩坑点循环条件、移动顺序、值比较第一坑是把循环条件写成while fast.next或while fast。链表没有环时快指针很可能走到最后一个节点这时再访问fast.next.next就是空引用异常。记住只有同时保证当前节点和下一个节点非空才可以安全地走两步。第二坑是移动顺序错误。有人习惯先把两个指针初始化在head然后先判断“是否相等”再移动结果第一轮就误判成有环因为slow和fast初始都指向同一个节点。正确顺序永远是先移动再判断。第三坑是用值而不是对象身份比较。两个不同节点的val可能相等如果环恰好没有出现在这两个节点处值比较会给出错误的True。用is或重载为引用比较的方式确保比较的是节点身份。还有一个不算坑但需要提的骚操作有人遍历时把每个节点的next改成指向自己用“是否访问过”来判断环。这个思路判断环本身可行但会破坏输入链表面试官通常不会接受工程中也绝对不能这么干。我建议你提都不要提除非你能在说出口的同时立刻补充“这是错误示范”。5.2 面试回答的正确节奏两分钟讲完一整套我参加过不少面试也模拟过不少次。这道题的高分回答节奏大概是这样的第一步30秒说思路。先提哈希表是可以做的但空间O(N)然后说用快慢指针可以做到O(1)空间。第二步40秒说正确性。慢指针进环后快指针已经在环内两者距离小于环长L快指针相对慢指针每轮逼近1步所以L轮以内必然相遇。第三步30秒写代码。把141题的实现写在白板上注意循环条件和is比较。第四步40秒说扩展。如果面试官问142题就补充第一次相遇后令一个指针从head出发slow从相遇点出发同速前进第二次相遇点就是环入口因为a (n-1)L c。这套节奏练顺之后你会发现环形链表这组题真正考察的不是“会不会写”而是“能不能在几分钟内用清晰的逻辑说服面试官”。而这恰恰是日常刷题时最容易忽略的训练。5.3 一变三环长度、链表相交、入口定位都可以复用吃透环形链表后你会发现好几个常考题都共用同一套思想。求环长度先用快慢指针找到相遇点然后让一个指针留在相遇点另一个指针从相遇点出发边绕边计数再次回到相遇点时走的步数就是环长。原理很简单相遇点本来就是环上的点从环上任意一点绕一整圈回到原点路程恰好是环周长。判断两个链表是否相交LeetCode 160可以把链表A的尾节点接到链表B的头节点上然后跑环形链表的判断。如果A、B相交那么从交点开始的后缀会被A的尾部接成环环的入口就是交点如果两链不相交则不会成环。用142题的detect方法找到环入口后再把被改动的next指针恢复成None就能既得到答案又不污染原链表。这些都是环形链表母题的分支理解了入口推导上面的变种基本不用额外背代码。我在实际刷题中的体会是环形链表这组题非常适合用来检验“背答案”和“真理解”的差别。如果你能不看代码在纸上完整写出a (n-1)L c的推导过程并且能随口说出“从相遇点到入口的距离是c加上若干整圈仍然到入口”这句话说明你真正拿下了它。我建议所有刚开始刷LeetCode的朋友把141和142连在一起练先写代码再画图再给一个完全不懂算法的人讲一遍。这个过程做完这组题基本就长在你脑子里了。最后再分享一个小习惯我每次复习链表题都会把常见的边界case比如单节点自环、双节点回环、长链接小环统统手动模拟一遍确保没有遗漏。环形链表这个坑我当初踩了不止一次希望这篇题解能帮你少走弯路。