代码随想录打卡走到第四天今天要啃的是快慢指针和环形链表。说实话刚开始看到“快慢指针”这个词我有点不以为然觉得无非就是把两个指针放到链表上跑。结果这一个小小的“跑”字背后藏着一整套跑圈模型甚至连数论里的同余方程都牵涉进来。这篇文章不是我复述题解而是我个人学习第四天的一份完整复盘从最直观的哈希表方案讲起解释为什么快指针偏偏要走两步把环入口的距离公式一步步推导出来再补充几个高频变体和我实际写代码时踩过的坑。刚接触链表题的人或者已经背过答案但始终没弄懂入口推导的人这篇应该都能找到点东西。1. 从“记节点”到“跑圈”快慢指针的思路是怎么来的1.1 哈希表方案直观但空间成本不小很多人第一次看到环形链表题第一反应都是用一个哈希集合把访问过的节点记下来。每遍历一个节点就先问一句“这个节点之前见过吗”如果见过说明链表又绕了回来如果没见过就把它加入集合继续往下走。这个方案的优点是几乎不会写错而且它不仅判断有环还能顺带找到环的入口——第一个重复出现的节点就是入口。我当时写出来的代码长这样def has_cycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False直白好懂。但它的代价是额外空间链表有N个节点集合就要存N个节点的引用空间复杂度是O(n)。刷题时N往往不大几十万都少见所以这个解法经常能通过评测但到了真实业务里一条百万级链表就会让内存占用明显涨上去。更麻烦的是如果链表节点类没有实现正确的哈希和相等逻辑放进集合前还得先改代码。我在本地用一个十万节点的随机链表试过哈希表版本的内存开销比快慢指针版本高出一个数量级趋势还是线性增长。对于追求稳定的服务端场景这个“直观”就显得有点贵。1.2 操场跑圈帮我把思路扭了过来快慢指针其实是一个经典的运动学模型两个人在圆形操场上同向跑步一个人快一个人慢只要时间足够快的人一定会追上慢的人因为快的人相对慢的人每圈都会多跑一段多出整整一圈后两人必然重合。链表成环后情况一模一样。把链表节点当成跑道把next指针当成前进方向慢指针每次走一个节点快指针每次走两个节点。快指针先进入环然后在环里面一圈圈跑慢指针最终也会进入环。从慢指针入环那一刻起快指针相对慢指针的速度等于“每操作一次接近一个节点”。环长是L的话最多跑L次两者就会相遇。反过来如果链表没有环快指针会先一步走到链表末尾撞上None这时就可以直接断定没有环。这个模型最大的价值在于判断有没有环不再依赖“记忆”。不需要set不需要额外的标记位只需要两个指针跑一跑看它们是否碰头。空间复杂度因此降到了O(1)。1.3 快慢指针成立的两个前提把代码默写下来不算难但我最早没搞明白的是为什么不能随便挑两个速度。后来总结出两个前提。第一个前提是起点必须相同。两个指针都要从head出发。如果有一个指针从中间某个节点开始相遇位置和环入口之间的数量关系就会被破坏后面找环入口的公式也就不成立了。第二个前提是速度差必须恒定而且最好是1。这里的“速度差”指快指针每一步移动的节点数减去慢指针每一步移动的节点数。标准写法是慢指针每次走1个节点快指针每次走2个节点速度差正好是1。如果改成慢1快3速度差是2虽然听起来也是“快慢指针”却可能在环里永远错过。原因我放在下一节详细说这一节先记住结论真正起作用的不是快指针比慢指针快多少倍而是两者之间每操作一次只拉开1个节点距离。2. 判环代码里“走两步”不是拍脑袋而是数学上最稳的选择2.1 最简判环实现先给出完整的判环代码def has_cycle(head): slow head 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因为循环体里马上要执行fast.next.next如果fast本身是Nonefast.next这一步就会崩如果fast.next是Nonefast.next.next也会崩两重判断缺一不可。第二相遇判断一定要放在指针移动之后。如果把if slow is fast写在循环开头slow和fast初始都指向head判环函数会对任何链表都返回True。第三比较指针要用is而不是因为我们要判断的是两个指针是否指向同一个对象而不是两个节点的值是否相等。虽然某些写法用也能碰巧通过但语义上is更准确。时间复杂度和空间复杂度需要单独说一句。无环时快指针遍历到链表末尾有环时两个指针在环内跑有限圈就会相遇整个过程仍然是O(n)。空间上只用了两个指针是O(1)。2.2 快指针走两步本质是速度差为1我最初有个误解以为“快指针走两步”是某个模板固定的要求。直到自己试着把代码改成快指针走三步发现有的用例会超时有的用例甚至会假死才意识到这里面的门道。关键在于速度差。假设快指针每次走v步慢指针每次走1步速度差d v - 1。当慢指针进入环时快指针可能已经在环内某处设此刻两个指针沿next方向的位置差为r。之后每操作一次这个位置差就加d取模环长L。能不能相遇等价于是否存在一个步数t使得d * t ≡ -r (mod L)这个数论方程有解的条件是d和L的最大公约数能整除r。当d1时1和任何L的最大公约数都是1所以无论r是多少方程一定有解也就是说无论如何都会相遇。但当d是2、3这类更大的数时事情就没那么美了。举个例子环长L4速度差d2如果r1位置差会按1、3、1、3循环永远不会变成0。这是因为gcd(2,4)2而r1不能被2整除方程无解。所以标准写法选择快2慢1不是因为“2”有什么魔法而是因为快2慢1的速度差正好是1能保证在任何环长、任何入环位置差下都必定相遇。2.3 边界条件需要用表格过一遍我习惯在做题前先列边界用例避免在循环条件上出错。输入情况期望结果head为NoneFalse单节点无环False单节点自环node.next nodeTrue偶数长度无环链False奇数长度无环链False整条链首尾相接全环True环入口在中部True容易漏的是自环和全环。自环就是node.next node第一次移动后slow和fast都会回到这个节点直接判定True。全环是尾节点接回头节点比如1 - 2 - 3 - 1这种情况下环长等于链表长度代码同样能正确处理。提示写判环和找入口两个函数之前最好先构造一批明确知道入口位置的测试链表再对比程序输出这样能一次性验证两项功能。3. 环入口的距离推导从head到入口的距离其实藏在相遇点里3.1 定义变量找环入口的经典算法分为两步第一步用快慢指针找到第一次相遇点第二步把一个指针放回head另一个留在相遇点然后两个指针都以每次一步的速度前进再次相遇的位置就是环入口。很多人知道这个算法但没做过推导。推导其实只用初中代数。先定义几个量a从head出发走到环入口节点需要经过的步数。L环的节点总数。b慢指针从环入口出发走了b步后与快指针第一次相遇。b可能为0也可能大于0。c从第一次相遇点出发继续走c步回到环入口。显然c L - b。需要注意的是在慢指针进入环之前快指针因为跑得快可能已经在环里绕了好几圈。所以快指针的总路程不能只写a加b还要把多绕的圈数加进去。3.2 关键等式快指针路程是慢指针的两倍第一次相遇时两个指针从head出发已经跑了一段时间。慢指针的总路程是slow_path a b快指针的总路程是fast_path a b nL这里的n表示快指针比慢指针多绕的完整圈数n至少是1。因为快指针的速度是慢指针的2倍所以快指针的路程也严格等于慢指针的2倍fast_path 2 * slow_path把两个式子代进去a b nL 2(a b)化简得到a b nL于是a nL - b (n-1)L (L - b) (n-1)L c这最后一行是整个算法的核心从head到环入口的距离a等于从第一次相遇点继续走到环入口的距离c再加上整数圈环长。换句话说只要从相遇点再走c步它已经回到了入口就算再多走几圈也仍然停在入口。3.3 第二次相遇为什么必定发生在入口第一次相遇后把fast放回headslow停在相遇点然后两个指针都每次走一步。head这边的指针走a步正好到达环入口。相遇点那边的slow指针也走a步。根据上面的式子a (n-1)L c。也就是说slow先走c步回到入口然后又完整转了(n-1)圈最终还是回到入口。两个指针同时到达入口于是第二次相遇点就是环入口。这里有个很微妙的点我们完全不需要知道n具体是几。n只影响“多绕几圈”不影响最后停下的位置。所以哪怕快指针在环里绕了几十圈才追上慢指针第二次同速行走依然会在入口准确相遇。3.4 完整代码和一个手算例子入口查找代码def detect_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: break else: return None fast head while slow is not fast: slow slow.next fast fast.next return slow第一次while用来找首次相遇。如果循环不是因为break退出而是正常结束说明快指针撞到了链表末尾没有环返回None。Python里的while...else恰好可以表达这个逻辑while正常结束会执行elsebreak跳出则不执行。手算验证一个例子1 - 2 - 3 - 4 - 5 - 3环入口是3环长L3。两个指针都从1出发。慢指针依次走1、2、3、4快指针依次走1、3、5、4。到第3步时两者都停在节点4这是第一次相遇。此时a2从1到3b1从3到4c2从4经过5回到3ab3正好等于nLn1。第二次循环开始fast回到head的节点1slow留在节点4。两个指针都走一步slow到5fast到2再走一步slow到3fast到3。两者在入口3相遇返回正确。还要注意一种边界情况如果环入口就是head比如1 - 2 - 3 - 1第一次相遇后fast回到head此时slow也还在相遇点第二次循环可能一开始就满足slow is fast直接返回head。这个场景不需要额外判断代码天然支持。4. 快慢指针的用法远不止判环几个我常用的变体4.1 找链表的中点快慢指针最常见的延伸应用是找链表的中点。逻辑和判环几乎一样快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好在中点。def find_mid(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next return slow节点数为奇数时比如1-2-3-4-5slow会停在3这是正中间。节点数为偶数时比如1-2-3-4这个写法会让slow停在3也就是靠右的中间节点。如果题目想要靠左的中间节点可以把while条件改成while fast.next and fast.next.next。这个细节在归并排序切分链表时特别重要切分位置不同递归子链表的起止就完全不同。4.2 找倒数第K个节点先拉出K步的“尺子”虽然不是“一快一慢”但这个变体和快慢指针是同一个思想利用两个指针之间的距离。先让快指针从头开始往前走K步然后快慢指针同步前进。当快指针到达链表末尾时慢指针和快指针之间正好差了K个节点所以慢指针指向倒数第K个节点。def find_from_end(head, k): fast head slow head for _ in range(k): if not fast: return None fast fast.next while fast: slow slow.next fast fast.next return slow这段代码需要注意的是如果链表长度小于k快指针在走K步的过程中会变成None需要提前返回。实际应用里“删除倒数第K个节点”就是在这一基础上再维护一个前驱节点避免丢失待删节点的前一个位置。4.3 判断回文链表找中点加反转的组合拳回文链表的常规解法有三步先用快慢指针找中点然后把中点之后的部分反转最后用两个指针从头和尾部同时向中间比较。def reverse_list(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev def is_palindrome(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next right reverse_list(slow) left head while right: if left.val ! right.val: return False left left.next right right.next return True实现不难但有一个经常被忽略的问题反转后半段会破坏原链表结构。如果这个链表在业务里还要继续使用比较完之后应该把后半段再反转回来。面试的时候如果能主动说到这一点会让对方觉得你是真考虑过工程问题而不只是在默写代码。4.4 一个非链表的例子用快慢指针识别“无限循环”快慢指针的思想其实是一种通用的环检测方法不一定要在链表里用。比如“快乐数”问题给定一个正整数反复把各个数位的平方加总得到新的数。如果最后能变成1就是快乐数如果陷入一个不包含1的循环就不是。这类问题可以建立一个隐式的“状态转移图”每个数指向下一个数。有人会用集合记录出现过的状态但同样可以用快慢指针慢指针每次算一次平方和快指针每次算两次。如果出现循环两个指针就会相遇如果最终是1快指针会先稳定停在1。这种抽象能力比背具体代码更重要。5. 实际调试中的坑和一套能打表的测试用例5.1 判空顺序引起的空指针异常我最早写判环代码时while条件写的是while fast.next and fast.next.next。这个写法在链表为空的一瞬间就会抛异常因为fast是Nonefast.next本身不可访问。正确写法必须把fast放在最前面while fast and fast.next这样在访问fast.next之前已经确认fast不为None。另一个相关的问题是有的同学会在循环体里单独加一道判断比如if not fast.next: return False再执行fast fast.next.next。这其实没有必要。只要while条件里已经保证fast.next不为None后面的fast.next.next最多只是None不会崩溃。增加无谓判断只会让逻辑更乱。5.2 找环入口时第二次循环的速度特别容易写错背代码最危险的地方在这里。第一次循环是快慢两倍速第二次循环很多人顺手也写成fast fast.next.next结果第二次相遇的地点就不一定在入口。第二次循环必须让两个指针都每次走一步。原因很简单我们希望从头出发的指针和从相遇点出发的指针以相同速度逼近入口。如果快指针继续用两倍速它就会在环里绕圈和慢指针相遇的位置仍然可能是环内任意点而不是入口。这个错误在代码评审里很常见我建议写完后先用1 - 2 - 3 - 4 - 5 - 3这个例子跑一遍看第二次相遇节点是不是3。5.3 用构造函数批量制造有环链表为了方便测试我通常先写一个辅助函数用来快速构造带环或不带环的链表。如果测试时还要一个一个手写节点效率太低。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def build_cycle(values, pos): if not values: return None head ListNode(values[0]) cur head for v in values[1:]: cur.next ListNode(v) cur cur.next if pos 0: entry head for _ in range(pos): entry entry.next cur.next entry return head配合这个辅助函数可以把下面这些用例直接打表构造参数含义期望结果build_cycle([], -1)空链表False / Nonebuild_cycle([1], -1)单节点无环False / Nonebuild_cycle([1], 0)单节点自环True / 入口节点1build_cycle([1,2,3,4,5], -1)无环长链False / Nonebuild_cycle([1,2,3,4,5], 2)环入口在节点3True / 入口节点3build_cycle([1,2,3,4,5,6], 0)整条链全环True / 入口节点1build_cycle([1,2,3,4,5,6], 5)环入口在节点6True / 入口节点6pos0代表尾节点接回头节点整条链成一个环。这类用例和“入口在中部”的用例放在一起测能确认第二次循环在入口等于head时也不会出错。5.4 调试技巧打印每轮指针位置如果你验证时发现结果不对不要急着盯着代码发呆。我自己的习惯是在两个循环里各打印一次slow和fast指向的节点值再用纸笔把运动过程画出来。第一次推导入口公式时我一直以为自己理解了打印出来才发现问题出在第二次循环开头没有把fast重新赋值回head导致第二次循环从相遇点继续跑整个程序直接跑飞。技巧把第一次相遇节点和第二次相遇节点的值都打出来再对照手动模拟。如果对不上大概率是变量定义没对齐比如把入口步数从0开始还是从1开始弄混了。这种细节在推导里很容易藏但在打印面前会立刻现形。如果你现在正在学这一块我建议别急着刷下一题。先把has_cycle和detect_cycle各跑一遍再把a nL - b这个等式自己推导一次最后试试不借助集合写出回文链表的判断。这套流程走完快慢指针才算是真正属于你的工具而不是背下来的模板。我第四天的笔记停在这里但链表的内容远没结束。记住这两个前提同起点、速度差为1之后遇到再难的环问题都能回到最朴素的跑圈模型上去。 
长河君 · 2026/10/19 13:52:57 · 阅读 1.2k 快慢指针与环形链表：从跑圈模型到环入口推导的完整复盘
代码随想录打卡走到第四天今天要啃的是快慢指针和环形链表。说实话刚开始看到“快慢指针”这个词我有点不以为然觉得无非就是把两个指针放到链表上跑。结果这一个小小的“跑”字背后藏着一整套跑圈模型甚至连数论里的同余方程都牵涉进来。这篇文章不是我复述题解而是我个人学习第四天的一份完整复盘从最直观的哈希表方案讲起解释为什么快指针偏偏要走两步把环入口的距离公式一步步推导出来再补充几个高频变体和我实际写代码时踩过的坑。刚接触链表题的人或者已经背过答案但始终没弄懂入口推导的人这篇应该都能找到点东西。1. 从“记节点”到“跑圈”快慢指针的思路是怎么来的1.1 哈希表方案直观但空间成本不小很多人第一次看到环形链表题第一反应都是用一个哈希集合把访问过的节点记下来。每遍历一个节点就先问一句“这个节点之前见过吗”如果见过说明链表又绕了回来如果没见过就把它加入集合继续往下走。这个方案的优点是几乎不会写错而且它不仅判断有环还能顺带找到环的入口——第一个重复出现的节点就是入口。我当时写出来的代码长这样def has_cycle(head): seen set() cur head while cur: if cur in seen: return True seen.add(cur) cur cur.next return False直白好懂。但它的代价是额外空间链表有N个节点集合就要存N个节点的引用空间复杂度是O(n)。刷题时N往往不大几十万都少见所以这个解法经常能通过评测但到了真实业务里一条百万级链表就会让内存占用明显涨上去。更麻烦的是如果链表节点类没有实现正确的哈希和相等逻辑放进集合前还得先改代码。我在本地用一个十万节点的随机链表试过哈希表版本的内存开销比快慢指针版本高出一个数量级趋势还是线性增长。对于追求稳定的服务端场景这个“直观”就显得有点贵。1.2 操场跑圈帮我把思路扭了过来快慢指针其实是一个经典的运动学模型两个人在圆形操场上同向跑步一个人快一个人慢只要时间足够快的人一定会追上慢的人因为快的人相对慢的人每圈都会多跑一段多出整整一圈后两人必然重合。链表成环后情况一模一样。把链表节点当成跑道把next指针当成前进方向慢指针每次走一个节点快指针每次走两个节点。快指针先进入环然后在环里面一圈圈跑慢指针最终也会进入环。从慢指针入环那一刻起快指针相对慢指针的速度等于“每操作一次接近一个节点”。环长是L的话最多跑L次两者就会相遇。反过来如果链表没有环快指针会先一步走到链表末尾撞上None这时就可以直接断定没有环。这个模型最大的价值在于判断有没有环不再依赖“记忆”。不需要set不需要额外的标记位只需要两个指针跑一跑看它们是否碰头。空间复杂度因此降到了O(1)。1.3 快慢指针成立的两个前提把代码默写下来不算难但我最早没搞明白的是为什么不能随便挑两个速度。后来总结出两个前提。第一个前提是起点必须相同。两个指针都要从head出发。如果有一个指针从中间某个节点开始相遇位置和环入口之间的数量关系就会被破坏后面找环入口的公式也就不成立了。第二个前提是速度差必须恒定而且最好是1。这里的“速度差”指快指针每一步移动的节点数减去慢指针每一步移动的节点数。标准写法是慢指针每次走1个节点快指针每次走2个节点速度差正好是1。如果改成慢1快3速度差是2虽然听起来也是“快慢指针”却可能在环里永远错过。原因我放在下一节详细说这一节先记住结论真正起作用的不是快指针比慢指针快多少倍而是两者之间每操作一次只拉开1个节点距离。2. 判环代码里“走两步”不是拍脑袋而是数学上最稳的选择2.1 最简判环实现先给出完整的判环代码def has_cycle(head): slow head 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因为循环体里马上要执行fast.next.next如果fast本身是Nonefast.next这一步就会崩如果fast.next是Nonefast.next.next也会崩两重判断缺一不可。第二相遇判断一定要放在指针移动之后。如果把if slow is fast写在循环开头slow和fast初始都指向head判环函数会对任何链表都返回True。第三比较指针要用is而不是因为我们要判断的是两个指针是否指向同一个对象而不是两个节点的值是否相等。虽然某些写法用也能碰巧通过但语义上is更准确。时间复杂度和空间复杂度需要单独说一句。无环时快指针遍历到链表末尾有环时两个指针在环内跑有限圈就会相遇整个过程仍然是O(n)。空间上只用了两个指针是O(1)。2.2 快指针走两步本质是速度差为1我最初有个误解以为“快指针走两步”是某个模板固定的要求。直到自己试着把代码改成快指针走三步发现有的用例会超时有的用例甚至会假死才意识到这里面的门道。关键在于速度差。假设快指针每次走v步慢指针每次走1步速度差d v - 1。当慢指针进入环时快指针可能已经在环内某处设此刻两个指针沿next方向的位置差为r。之后每操作一次这个位置差就加d取模环长L。能不能相遇等价于是否存在一个步数t使得d * t ≡ -r (mod L)这个数论方程有解的条件是d和L的最大公约数能整除r。当d1时1和任何L的最大公约数都是1所以无论r是多少方程一定有解也就是说无论如何都会相遇。但当d是2、3这类更大的数时事情就没那么美了。举个例子环长L4速度差d2如果r1位置差会按1、3、1、3循环永远不会变成0。这是因为gcd(2,4)2而r1不能被2整除方程无解。所以标准写法选择快2慢1不是因为“2”有什么魔法而是因为快2慢1的速度差正好是1能保证在任何环长、任何入环位置差下都必定相遇。2.3 边界条件需要用表格过一遍我习惯在做题前先列边界用例避免在循环条件上出错。输入情况期望结果head为NoneFalse单节点无环False单节点自环node.next nodeTrue偶数长度无环链False奇数长度无环链False整条链首尾相接全环True环入口在中部True容易漏的是自环和全环。自环就是node.next node第一次移动后slow和fast都会回到这个节点直接判定True。全环是尾节点接回头节点比如1 - 2 - 3 - 1这种情况下环长等于链表长度代码同样能正确处理。提示写判环和找入口两个函数之前最好先构造一批明确知道入口位置的测试链表再对比程序输出这样能一次性验证两项功能。3. 环入口的距离推导从head到入口的距离其实藏在相遇点里3.1 定义变量找环入口的经典算法分为两步第一步用快慢指针找到第一次相遇点第二步把一个指针放回head另一个留在相遇点然后两个指针都以每次一步的速度前进再次相遇的位置就是环入口。很多人知道这个算法但没做过推导。推导其实只用初中代数。先定义几个量a从head出发走到环入口节点需要经过的步数。L环的节点总数。b慢指针从环入口出发走了b步后与快指针第一次相遇。b可能为0也可能大于0。c从第一次相遇点出发继续走c步回到环入口。显然c L - b。需要注意的是在慢指针进入环之前快指针因为跑得快可能已经在环里绕了好几圈。所以快指针的总路程不能只写a加b还要把多绕的圈数加进去。3.2 关键等式快指针路程是慢指针的两倍第一次相遇时两个指针从head出发已经跑了一段时间。慢指针的总路程是slow_path a b快指针的总路程是fast_path a b nL这里的n表示快指针比慢指针多绕的完整圈数n至少是1。因为快指针的速度是慢指针的2倍所以快指针的路程也严格等于慢指针的2倍fast_path 2 * slow_path把两个式子代进去a b nL 2(a b)化简得到a b nL于是a nL - b (n-1)L (L - b) (n-1)L c这最后一行是整个算法的核心从head到环入口的距离a等于从第一次相遇点继续走到环入口的距离c再加上整数圈环长。换句话说只要从相遇点再走c步它已经回到了入口就算再多走几圈也仍然停在入口。3.3 第二次相遇为什么必定发生在入口第一次相遇后把fast放回headslow停在相遇点然后两个指针都每次走一步。head这边的指针走a步正好到达环入口。相遇点那边的slow指针也走a步。根据上面的式子a (n-1)L c。也就是说slow先走c步回到入口然后又完整转了(n-1)圈最终还是回到入口。两个指针同时到达入口于是第二次相遇点就是环入口。这里有个很微妙的点我们完全不需要知道n具体是几。n只影响“多绕几圈”不影响最后停下的位置。所以哪怕快指针在环里绕了几十圈才追上慢指针第二次同速行走依然会在入口准确相遇。3.4 完整代码和一个手算例子入口查找代码def detect_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: break else: return None fast head while slow is not fast: slow slow.next fast fast.next return slow第一次while用来找首次相遇。如果循环不是因为break退出而是正常结束说明快指针撞到了链表末尾没有环返回None。Python里的while...else恰好可以表达这个逻辑while正常结束会执行elsebreak跳出则不执行。手算验证一个例子1 - 2 - 3 - 4 - 5 - 3环入口是3环长L3。两个指针都从1出发。慢指针依次走1、2、3、4快指针依次走1、3、5、4。到第3步时两者都停在节点4这是第一次相遇。此时a2从1到3b1从3到4c2从4经过5回到3ab3正好等于nLn1。第二次循环开始fast回到head的节点1slow留在节点4。两个指针都走一步slow到5fast到2再走一步slow到3fast到3。两者在入口3相遇返回正确。还要注意一种边界情况如果环入口就是head比如1 - 2 - 3 - 1第一次相遇后fast回到head此时slow也还在相遇点第二次循环可能一开始就满足slow is fast直接返回head。这个场景不需要额外判断代码天然支持。4. 快慢指针的用法远不止判环几个我常用的变体4.1 找链表的中点快慢指针最常见的延伸应用是找链表的中点。逻辑和判环几乎一样快指针每次走两步慢指针每次走一步快指针到末尾时慢指针正好在中点。def find_mid(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next return slow节点数为奇数时比如1-2-3-4-5slow会停在3这是正中间。节点数为偶数时比如1-2-3-4这个写法会让slow停在3也就是靠右的中间节点。如果题目想要靠左的中间节点可以把while条件改成while fast.next and fast.next.next。这个细节在归并排序切分链表时特别重要切分位置不同递归子链表的起止就完全不同。4.2 找倒数第K个节点先拉出K步的“尺子”虽然不是“一快一慢”但这个变体和快慢指针是同一个思想利用两个指针之间的距离。先让快指针从头开始往前走K步然后快慢指针同步前进。当快指针到达链表末尾时慢指针和快指针之间正好差了K个节点所以慢指针指向倒数第K个节点。def find_from_end(head, k): fast head slow head for _ in range(k): if not fast: return None fast fast.next while fast: slow slow.next fast fast.next return slow这段代码需要注意的是如果链表长度小于k快指针在走K步的过程中会变成None需要提前返回。实际应用里“删除倒数第K个节点”就是在这一基础上再维护一个前驱节点避免丢失待删节点的前一个位置。4.3 判断回文链表找中点加反转的组合拳回文链表的常规解法有三步先用快慢指针找中点然后把中点之后的部分反转最后用两个指针从头和尾部同时向中间比较。def reverse_list(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev def is_palindrome(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next right reverse_list(slow) left head while right: if left.val ! right.val: return False left left.next right right.next return True实现不难但有一个经常被忽略的问题反转后半段会破坏原链表结构。如果这个链表在业务里还要继续使用比较完之后应该把后半段再反转回来。面试的时候如果能主动说到这一点会让对方觉得你是真考虑过工程问题而不只是在默写代码。4.4 一个非链表的例子用快慢指针识别“无限循环”快慢指针的思想其实是一种通用的环检测方法不一定要在链表里用。比如“快乐数”问题给定一个正整数反复把各个数位的平方加总得到新的数。如果最后能变成1就是快乐数如果陷入一个不包含1的循环就不是。这类问题可以建立一个隐式的“状态转移图”每个数指向下一个数。有人会用集合记录出现过的状态但同样可以用快慢指针慢指针每次算一次平方和快指针每次算两次。如果出现循环两个指针就会相遇如果最终是1快指针会先稳定停在1。这种抽象能力比背具体代码更重要。5. 实际调试中的坑和一套能打表的测试用例5.1 判空顺序引起的空指针异常我最早写判环代码时while条件写的是while fast.next and fast.next.next。这个写法在链表为空的一瞬间就会抛异常因为fast是Nonefast.next本身不可访问。正确写法必须把fast放在最前面while fast and fast.next这样在访问fast.next之前已经确认fast不为None。另一个相关的问题是有的同学会在循环体里单独加一道判断比如if not fast.next: return False再执行fast fast.next.next。这其实没有必要。只要while条件里已经保证fast.next不为None后面的fast.next.next最多只是None不会崩溃。增加无谓判断只会让逻辑更乱。5.2 找环入口时第二次循环的速度特别容易写错背代码最危险的地方在这里。第一次循环是快慢两倍速第二次循环很多人顺手也写成fast fast.next.next结果第二次相遇的地点就不一定在入口。第二次循环必须让两个指针都每次走一步。原因很简单我们希望从头出发的指针和从相遇点出发的指针以相同速度逼近入口。如果快指针继续用两倍速它就会在环里绕圈和慢指针相遇的位置仍然可能是环内任意点而不是入口。这个错误在代码评审里很常见我建议写完后先用1 - 2 - 3 - 4 - 5 - 3这个例子跑一遍看第二次相遇节点是不是3。5.3 用构造函数批量制造有环链表为了方便测试我通常先写一个辅助函数用来快速构造带环或不带环的链表。如果测试时还要一个一个手写节点效率太低。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def build_cycle(values, pos): if not values: return None head ListNode(values[0]) cur head for v in values[1:]: cur.next ListNode(v) cur cur.next if pos 0: entry head for _ in range(pos): entry entry.next cur.next entry return head配合这个辅助函数可以把下面这些用例直接打表构造参数含义期望结果build_cycle([], -1)空链表False / Nonebuild_cycle([1], -1)单节点无环False / Nonebuild_cycle([1], 0)单节点自环True / 入口节点1build_cycle([1,2,3,4,5], -1)无环长链False / Nonebuild_cycle([1,2,3,4,5], 2)环入口在节点3True / 入口节点3build_cycle([1,2,3,4,5,6], 0)整条链全环True / 入口节点1build_cycle([1,2,3,4,5,6], 5)环入口在节点6True / 入口节点6pos0代表尾节点接回头节点整条链成一个环。这类用例和“入口在中部”的用例放在一起测能确认第二次循环在入口等于head时也不会出错。5.4 调试技巧打印每轮指针位置如果你验证时发现结果不对不要急着盯着代码发呆。我自己的习惯是在两个循环里各打印一次slow和fast指向的节点值再用纸笔把运动过程画出来。第一次推导入口公式时我一直以为自己理解了打印出来才发现问题出在第二次循环开头没有把fast重新赋值回head导致第二次循环从相遇点继续跑整个程序直接跑飞。技巧把第一次相遇节点和第二次相遇节点的值都打出来再对照手动模拟。如果对不上大概率是变量定义没对齐比如把入口步数从0开始还是从1开始弄混了。这种细节在推导里很容易藏但在打印面前会立刻现形。如果你现在正在学这一块我建议别急着刷下一题。先把has_cycle和detect_cycle各跑一遍再把a nL - b这个等式自己推导一次最后试试不借助集合写出回文链表的判断。这套流程走完快慢指针才算是真正属于你的工具而不是背下来的模板。我第四天的笔记停在这里但链表的内容远没结束。记住这两个前提同起点、速度差为1之后遇到再难的环问题都能回到最朴素的跑圈模型上去。