刷链表题刷到一定数量之后你会发现有不少题目都在围着“遍历”打转——找中点、找倒数第几个、判断有没有环、判断是不是回文。这些题表面长得不一样解法却共享同一个套路让两个指针以不同速度往后走。这个套路在数据结构里叫快慢指针也有人叫龟兔赛跑算法。我最早是在《数据结构》课程里接触这个概念后来刷 LeetCode 时发现它是链表题的隐藏主角甚至还能反杀到数组里解决找重复数这类问题。这篇文章就把快慢指针讲透。内容按实战逻辑展开先解释两个指针为什么能“一个追一个”再逐个拆环形链表、入环点、链表中点、倒数第 k 个、回文链表这些高频场景每个场景都给出可复现代码和边界分析最后分享我实际调试中踩过的坑。无论你是正在准备考研 408 数据结构还是刷算法题找工作或者只是想补一补基本功这篇都能让你从“听说过快慢指针”变成“能用快慢指针解题”。1. 快慢指针两个指针的“速度差”能做什么1.1 先理解最基本的直觉快慢指针的思想一句话就能说完在一条链表上同时派出两个指针一个每次走一步一个每次走两步利用速度差来感知链表的结构特征。这句话听起来平淡但背后藏着一个关键的数学模型——相对速度。想象两个人在圆形操场上跑步一个人慢跑一个人快跑。只要跑得足够久快的人一定会从慢的人身后追上来哪怕操场是弯的。这个追上的过程不需要知道操场具体有多长也不需要知道两个人起点相差多远只要速度不同、轨道闭合相遇就是必然。链表里的“环”就是这个闭合操场。快指针走两步、慢指针走一步相对速度是每轮追近一个节点。只要链表存在环两个指针早晚会相遇。如果在链表尾部的 null 处快指针先撞墙说明没有环。这个直觉看起来简单却是整个快慢指针体系的源头。判断是否有环、找环入口、求链表中点全都是这个直觉的不同变形。1.2 为什么快指针每次走两步而不是三步、四步有人会问快指针想追上慢指针走快点不是更省时间吗真实场景中走三步、四步也能判断有环为什么主流的实现一致选择“每次两步”答案与“环的长度”和“相对速度”有关。如果快指针每次比慢指针多走一个节点那相对速度就是1。两个指针之间的距离差最大也就是环的长度 C。所以最多经过 C 轮就一定追上。复杂度可控逻辑简单。相对速度一旦超过 1分析就会多出很多麻烦。比如快指针一次走三步相对速度是 2那么当初始距离差不是 2 的倍数时指针可能会擦肩而过导致需要多判断一圈甚至提前落到 null。最极端的情况是在短环里快指针还没追上慢指针自己已经一步跳过了唯一出口直接从环上“跳”到了链表尾。虽然这种情况通常可以通过边界条件规避但实现起来细节更多收益却几乎没有。还有一个更微妙的问题速度差太大时快指针可能在一次移动中“跨过”慢指针所在节点。在链表这种线性结构里跨过意味着两者不会在这一轮相遇要多跑几轮才能碰上。虽然不影响最终结论但推导和分析就绕了远路。所以每次两步是工程上的平衡点保证相遇必然性的同时把复杂度控制在 O(n)。1.3 时间复杂度与空间复杂度所有用快慢指针解决的链表问题都在 O(n) 时间内完成额外空间 O(1)——这恰恰是它最大的价值。拿“判断链表是否有环”来说主流替代方案是哈希表遍历链表时把每个节点地址存进集合如果碰到已经存在的地址说明有环。哈希表方案在时间上是 O(n)但空间是 O(n)。链表很长时哈希表占用可能达到几百兆而快慢指针方案只需要两个指针变量内存开销是常量级。在面试和考试场景里空间复杂度的差别往往是决定性因素。题目如果加上“只能使用 O(1) 额外空间”的约束哈希表方案直接出局。这也就是为什么快慢指针在《数据结构》教材和面试题里地位极高。2. 环形链表与入环点快慢指针的名场面2.1 判断链表是否有环LeetCode 141 是快慢指针的入门题给定一个链表的头节点判断链表中是否有环。完整思路是设置 slow 和 fast 两个指针初始都指向 head。循环条件是 fast 不为空且 fast.next 不为空。每轮循环 slow 走一步、fast 走两步。如果在循环过程中 slow fast说明链表有环如果循环正常终止说明链表无环。有人第一次接触时会有一个困惑slow 会不会永远等不到 fast不会。因为 fast 总比 slow 快fast 闯入环内之后会不断缩短两者之间的距离。每次缩短一个节点最多绕环一整圈就能追上。这个“追上”的过程恰好证明了环的存在。C 语言实现很经典bool hasCycle(struct ListNode *head) { if (head NULL || head-next NULL) { return false; } struct ListNode *slow head; struct ListNode *fast head-next; while (slow ! fast) { if (fast NULL || fast-next NULL) { return false; } slow slow-next; fast fast-next-next; } return true; }这里有个容易被忽略的细节上面的写法让 fast 初始指向 head-next而不是 head。这样做的目的是让循环条件变成 slow ! fast避免初始相同导致循环根本不进入。很多版本的教材会写成 fast 初始也指向 head然后用 do-while 风格保证先跑一轮再比较两种写法都可以但初学者容易把两者混在一起。我自己的习惯是慢指针每轮先走一步、快指针每轮先走两步然后判断是否相等循环条件用 while (fast fast-next) 来控制更直观bool hasCycle(struct ListNode *head) { struct ListNode *slow head; struct ListNode *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; }两种写法结果一样但第二种的退出条件更清晰快指针走到空指针说明链表有尽头必然没有环。Python 版本更贴近刷题场景def hasCycle(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False2.2 找入环点经典距离推导判断有环只是第一步。很多题目更进一步不仅要判断有环还要返回环的入口节点。这就是 LeetCode 142。解法分两阶段。第一阶段用快慢指针找到第一次相遇点第二阶段把 fast 放回头节点改为两个指针都走一步第二次相遇的位置就是环入口。第一次听到这个解法的人都会一脸懵为什么第二次相遇就是入口这里必须把距离算一遍。假设链表头到环入口的距离是 a环入口到第一次相遇点的距离是 b沿着前进方向相遇点继续走到环入口的距离是 c。那么环的长度就是 b c。慢指针从链表头出发到第一次相遇时一共走了 a b。快指针速度是慢指针的两倍所以快指针走了 2(a b)。同时快指针从链表头出发绕了 n 圈环之后到达相遇点也可以表示为 a b n(b c)。两个式子联立快指针路程 2(a b)快指针路程 a b n(b c)所以2(a b) a b n(b c) a b n(b c) a n(b c) - b (n - 1)(b c) c当 n 1 时a c。也就是说从链表头走到环入口的距离等于从第一次相遇点继续走到环入口的距离。所以第二阶段让一个指针从链表头出发、另一个指针从相遇点出发都走一步相遇之处必然就是环入口。当 n 1 时结论是 a (n - 1)(b c) c形式上是先绕了 n-1 圈再走 c 的距离而绕圈不会改变相对位置所以两个指针仍然会在环入口碰上。C 语言实现如下struct ListNode *detectCycle(struct ListNode *head) { struct ListNode *slow head; struct ListNode *fast head; int hasCycle 0; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { hasCycle 1; break; } } if (!hasCycle) { return NULL; } fast head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; }第二阶段没必要让 fast 和 slow 再分谁快谁慢统一走一步就行。这个解法对面试官非常友好因为你能证明“为什么相遇点走到底就是入环点”而不是死记硬背结论。2.3 环与链表的长度关系要怎么算找入环点之外偶尔还有题目要算链表总长度或环的长度。环的长度可以从第一次相遇点开始继续走一圈回到相遇点记录步数。链表总长度则是链表头到入环点的距离a加上环的长度。这一块没有新的算法核心还是在快慢指针的基础上补充一次遍历。不要小看这些变体考研题和面试题经常把“判环”和“求长度”放在同一个答题流程里考的是你是否真正理解了指针从哪儿出发、在哪儿停下。3. 中间节点、倒数第k个与回文判断快慢指针的日常用法3.1 找链表的中间节点路径慢指针每次走一步快指针每次走两步。当快指针走到链表末尾时慢指针刚好停在中间位置。LeetCode 876 就是原题。对偶数长度的链表题目要求返回第二个中间节点。使用“fast 从 head 出发每次走两步slow 从 head 出发每次走一步”的方式当 fast 走到 null 时slow 正好指向第二个中间节点。代码非常简洁def middleNode(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slow这里最值得讲的是“为什么停在中间”。链表长度为奇数 n 时fast 走到最后一个节点slow 走了 (n-1)/2 步停在正中间链表长度为偶数 n 时fast 走到 nullslow 走了 n/2 步停在靠右的中间节点。这个行为刚好满足题目要求不需要额外判断长度奇偶。如果题目要求偶数长度时返回靠左的中间节点只需要 slow 初始指向 headfast 初始指向 head-next就能避开。找中间节点之所以重要不只是因为题目本身而是因为它是一切“切开链表”操作的前置步骤。回文判断、链表排序、构建平衡二叉树都会先用快慢指针找到中点。3.2 寻找倒数第 k 个节点倒数第 k 个节点不需要快慢速度差但用的是同一种指针配合思想。思路是fast 先走 k 步然后 slow 和 fast 一起走一步直到 fast 走到 null。此时 slow 恰好指向倒数第 k 个节点。这个做法本质上是让 slow 和 fast 之间保持长度为 k 的窗口。fast 先跑 k 步确定了窗口右侧然后窗口整体平移直到右侧顶到链表尾。代码def findFromEnd(head, k): slow head fast head for _ in range(k): if not fast: return None fast fast.next while fast: slow slow.next fast fast.next return slow边界条件是 k 大于链表长度。循环里 fast 提前碰到 null直接返回 None。这也是比“先遍历一遍求总长度再走 n-k 步”更优雅的做法因为它只需要一次遍历。我处理这类题的核心感受是快慢指针本质上就是“窗口滑动”的链表版你让两个指针保持固定距离或者保持固定相对速度信息自然浮出水面。3.3 回文链表快慢指针和反转的配合回文链表LeetCode 234是快慢指针最典型的复合应用。判断一个链表是不是回文第一反应是用栈或者数组存下来再比对但那样空间复杂度是 O(n)。快慢指针方案只需要 O(1) 额外空间。思路分三步用快慢指针找到链表中间节点。从中间节点之后的部分反转链表。从头节点和反转后的头节点同时遍历逐节点比较值。完整 Python 实现def isPalindrome(head): if not head or not head.next: return True slow head fast head while fast and fast.next: slow slow.next fast fast.next.next prev None curr slow while curr: nxt curr.next curr.next prev prev curr curr nxt left head right prev while right: if left.val ! right.val: return False left left.next right right.next return True这个解法把快慢指针和链表反转结合到一起是“基础算法组合拳”的典型。面试时能写出这个方案比用栈存储再比较的方案加分不少因为你的空间复杂度做到了最优。值得提醒的是判断回文前如果先找到中点是第二个中间节点反转后半段之后链表长度是偶数时两边完全对应是奇数时右侧链表比左侧短一个节点所以比较时只以 right 不为空作为循环条件不会出现越界。4. 边界条件、常见坑位与调试实录4.1 空链表和单节点链表的处理快慢指针代码的第一行几乎都是空指针检查。head 为空或者 head.next 为空很多题都可以直接返回。这个“直接返回”很容易被忽略但遗漏之后代码会在 while 条件里访问空指针的 next直接崩溃。我见过最多的错误就是循环条件写得不够宽松。判断有环时如果链表是单节点且自环那 head.next head快指针走两步会回到自身检测逻辑没问题。如果链表是单节点但没有环快指针从 head-next 出发会立刻变成 NULL必须在 while 条件里写 fast ! NULL fast-next ! NULL否则解引用空指针就是事故现场。规则可以简单记只要快指针要连续走两步就必须保证 fast 和 fast.next 都不为空。这是快慢指针代码的第一条安全准则。4.2 fast 初始位置的选择判断有环的代码里fast 初始可以指向 head也可以指向 head-next。这个选择会改变循环结构fast head 时初始 slow fast必须用 do-while 或者先移动后比较否则循环不会进入。fast head-next 时初始 slow ! fast可以直接进入 while (slow ! fast) 循环。很多刷题新手把不同的初始条件抄混了导致代码陷入死循环或者直接跳出不判断。想避免这个问题建议固定一种模板fast 初始等于 head循环用 while (fast fast-next)每轮先移动再比较。这个模板在判断有环、寻找入环点、找中间节点时都能复用不容易记错。4.3 相遇一定会发生但慢指针不会在环里转圈查看代码时有人会追问如果环很长快指针追上慢指针要很久吗其实不需要。前面推导过相对速度是 1所以追上所需的轮数不会超过环长。更重要的结论是慢指针在环里最多走不完一圈就会被追上。慢指针进环之前快指针已经进环一段时间了它可能正在环里某个位置等它。慢指针进环后每走一个节点快指针逼近一步两者距离减一。由于两者初始距离小于环长慢指针走完一圈之前快指针必然已经追上。这个结论在找入环点阶段特别有用因为它保证相遇点发生在慢指针第一次进入环后不久数学推导里的 b 和 c 的关系也能保持稳定。4.4 快慢指针 vs 哈希表什么时候用哪种快慢指针并不总是最优解。如果题目只要求判断是否存在环而且不限制空间复杂度哈希表在思路上更直接代码也更不容易出错。哈希表方案的流程遍历链表每到一个节点就把地址存进 set 或 map。如果发现当前节点已经存在说明有环。这个方案的优势是天然支持“找到具体节点”——存的是完整指针不是值。快慢指针方案的唯一缺点是数学理解门槛略高面试时需要现场推导。但它的空间复杂度碾压哈希表面对大数据量链表时优势明显。实际建议是练习题必须快慢指针和哈希表两种都写一遍面试时优先说快慢指针因为能展示你掌握了 O(1) 空间的解法同时还能讲解原理笔试或者牛客网这种需要快速 AC 的场景用你最熟练的那个。4.5 调试快慢指针代码的一个实用方法链表题的调试一直比数组题麻烦。节点地址在内存里不连续没法一眼看出谁是谁。我的习惯是写一个辅助函数把链表的节点值按顺序打印出来如果怀疑有环或者循环异常就在里加一个计数器最多循环 1000 次强制退出打印出 slow 和 fast 各自指向的值。这个方法很多教程不会提但排查死循环时特别好用。尤其是自己构造测试链表时用了带环的用例如果不限制循环次数程序会一直跑你甚至分不清是代码逻辑错了还是确实在环里没出来。5. 从链表到数组快慢指针的进阶玩法5.1 循环数组检测快慢指针不仅能处理链表还能处理数组。LeetCode 457 就是一道典型的“循环数组”题数组每个元素表示下一步要移动的步数正值向右走负值向左走问数组中是否存在一个满足条件的循环。这类问题把数组下标看成一个虚拟链表节点下标 i 通过 nums[i] 的值计算出下一个下标也就是“下一步的指针”。于是数组就变成了一个有节点、有边的图遍历问题。快慢指针用在这条虚拟链表上判断是否存在闭环。因为数组下标是连续的判断是否回到同一个下标就能确定环。这个题目比链表判环多一个限制条件循环的方向必须全部相同即不能一个节点向右、一个节点向左。所以实现时除了快慢指针还要记录每一步的方向。5.2 数组里的“找重复数”为什么能用龟兔赛跑LeetCode 287 是另一道看上去和链表毫无关系的题目给定一个包含 n1 个整数的数组每个整数在 1 到 n 之间至少存在一个重复整数找出这个重复数。要求不能修改数组只能用 O(1) 空间。解法居然还是快慢指针。思路是把数组值当作索引去访问形成一张隐式链表从 index 0 出发nums[0] 是下一个索引从该索引出发nums[nums[0]] 是再下一个索引以此类推因为有重复元素必然有两个不同下标映射到同一个值这张隐式链表里必然存在环。环的入口对应的值就是重复数。这个过程和“找链表的入环点”如出一辙第一阶段快慢指针相遇第二阶段从起点和相遇点同时走直到再次相遇相遇处的索引就是重复元素。这个解法巧妙的地方在于把数组下标和值互相映射构造出一个虚拟链表而龟兔赛跑算法刚好用于这个虚拟链表。5.3 进阶题的组合规律观察这些进阶题可以发现一个模式快慢指针本质上是一种图遍历算法只不过作用在“线性但可能存在回环”的结构上。链表、循环数组、隐式映射图这些结构都可以抽象成节点和边快慢指针判断的核心就是“是否存在回环”。掌握了这个抽象看到貌似无关的题就不会慌。先问一句这个结构能不能变成一张图这张图是不是可能有环如果都能快慢指针就值得一试。在我自己的刷题节奏里快慢指针是少数几个我愿意反复回看的算法。它的第一眼看上去很绕可一旦理解了相对速度、入环点距离推导后面所有变体都能自然推导出来。比死记十道题模板有意义得多。6. 配套练习与常见误区速查6.1 练习顺序建议单独讲一个算法不配几道练习题等于白讲。我建议按下面顺序刷由浅入深LeetCode 141 判断链表是否有环LeetCode 876 链表的中间节点LeetCode 142 寻找环形链表的入口节点LeetCode 234 回文链表LeetCode 287 寻找重复数LeetCode 457 环形数组循环前四题覆盖了链表场景的全部基础第五题打破“只能用于链表”的思维定式第六题把方向约束加进来算是对快慢指针的完整练手。6.2 高频误区一览结合我自己被坑过的经验和看别人踩过的坑这个算法有以下几个高频误区误区正确理解认为快指针必须从 head 出发判断环时 fast 可以指向 head 或 head-next关键是循环结构要匹配认为快指针速度越快越好每次两步是工程最优解速度快了容易跨过慢指针且推导复杂认为找到相遇点就能直接确认入环点需要第二阶段一个指针回头节点两个指针都走一步二次相遇才是入环点处理回文时忘记反转后半段回文判断除了快慢指针还需要配合反转操作两个基础操作缺一不可在数组“找重复数”里忘了隐式链表映射必须把 nums[i] 当作 next 指针不能直接当作链表节点6.3 一套模板打天下最后分享一个非常实用的个人经验快慢指针题虽然看起来多变核心模板就一套。判断环、找入口、找中点本质上都是同一套移动逻辑。def twoPointersTemplate(head): if not head or not head.next: return None slow head fast head while fast and fast.next: slow slow.next fast fast.next.next # 根据题目要求在这里做判断 return slow其余代码都是在这个模板上做加减法判断有环就检查 slow fast找中点就注意循环结束时 slow 的位置找入口就把 fast 移回头节点再同步走。这套模板写顺手之后面试时碰到链表类题目思路会被拉回这个框架答题速度快很多。我个人在备考和面试阶段都是这么练的建议你也直接在这个骨架上针对性改条件别每次重新从零设计算法逻辑。