说实话链表这块的知识点我在前面的系列里已经整理过不少从单链表的增删改查到反转、合并都聊过但“快慢指针”一直没单独拎出来写。倒不是因为它不重要恰恰相反这是链表题里最容易让初学者眼前一亮、又最容易在细节上翻车的一个技巧。我印象很深当年在 LeetCode 上第一次看到环形链表检测的题解心里想的是“卧槽还能这么玩”——两个指针一个走一步一个走两步就能判断有没有环、还能找到入口空间复杂度还是 O(1)。这种设计思路放在考研数据结构里也属于那种“看着简单、推导起来全是细节”的考点。这篇是系列第十五篇我打算把快慢指针彻底讲透从最底层的相遇原理到环形链表入口的数学推导再到找中点、倒数第 k 个节点、回文判断这些高频应用最后再聊几个我实际写代码时踩过的坑。无论你是为了应付期末考试、408 统考还是在刷 LeetCode 准备面试这篇文章都能当一份可以直接复用的参考。1. 快慢指针到底在解决什么问题两次遍历变一次、空间降成 O(1)1.1 快慢指针的定义和直观理解快慢指针其实就是两个同向移动的指针起点都是链表头节点但每次移动的步数不一样。最常见的是慢指针每次走 1 步快指针每次走 2 步。这两个指针在同一条链表上运动因为速度不同它们之间的距离会不断变化这种“位置差”本身就是信息。用一个操场跑圈的类比你马上就懂了假如你和朋友在一个圆形跑道上从同一起点同向出发你跑得比他快那么只要跑道是闭合的你总会在某一圈追上他、甚至超过他。反过来如果跑道是直线的速度快的那个人永远不可能“追上”速度慢的那个人——因为后者在前者前方距离只会越拉越远。这个“会不会追上”的结论恰好能用来判断链表里是否存在环。这就是快慢指针最朴素的直觉来源。1.2 三类最典型的应用场景快慢指针在数据结构题目里的应用远不止判环一个。我整理了一下面试和考试里出现频率最高的就三类场景核心思路典型题目复杂度环形链表检测快慢指针若能在环内相遇说明链表存在环利用二次相遇可定位入口LeetCode 141、142剑指 Offer 23时间 O(n)空间 O(1)找链表中点快指针到末尾时慢指针停在中间位置LeetCode 876、148回文链表 234时间 O(n)空间 O(1)找倒数第 k 个节点快指针先走 k 步再与慢指针同步走快指针到尾时慢指针即倒数第 kLeetCode 19剑指 Offer 22时间 O(n)空间 O(1)这三类问题用常规思路做其实都不难判环可以用哈希表记住访问过的节点找中点可以先遍历一遍拿到链表长度再走 n/2 步找倒数第 k 个也可以先算长度。但所有常规做法都有一个共同代价——要么需要额外的空间要么需要两轮遍历。快慢指针的高明之处就是把“第二轮遍历”省掉了把额外的哈希表也省掉了一次循环同时完成任务。1.3 为什么不是哈希表方案很多人会想凭啥非要学快慢指针我能用哈希表解决不就行了吗。确实哈希表方案逻辑上更直白每遍历一个节点就把它的地址存进集合如果某个地址重复出现就说明有环。但在实际场景里O(n) 的额外空间并不总是可以接受的。比如你在嵌入式设备上处理一个超长的链表内存本来就很紧张又比如面试官就是想考察你能否写出空间 O(1) 的解法。哈希表方案在这些场景下就属于“能过但不够好”。更重要的是快慢指针的空间 O(1) 特性让它可以扩展到“无法用哈希表直接标记”的场景——比如后面的数组状态下找重复数以及处理数据流的场景。因为不必记录全部历史状态它天然适合那些我们只能看到当前节点、不能回头访问的环境。这也是快慢指针在算法设计里地位这么高的根本原因。2. 环形链表检测从“会不会死循环”到入口点的数学推导2.1 判环为什么第一次相遇一定发生先看最简单的问题给定一个链表的头节点判断链表中是否有环。常规的哈希表写法是遍历而快慢指针写法是这样struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; bool hasCycle(ListNode *head) { if (head nullptr || head-next nullptr) { return false; } ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; }为什么这个算法一定能判断出环的存在关键在相对速度。假设链表存在一个长度为 L 的环当慢指针刚刚进入环的入口时快指针已经在环内走了若干圈此时两个指针都在环内它们之间的“距离差”一定是环长 L 的整数倍减去某个值——本质上等价于快指针落后慢指针 d 步d L。每一轮循环快指针相对慢指针多走 1 步所以距离差会从 d 变成 d-1、d-2……一直变到 0也就是两者相遇。这个过程是必然发生的因为它是一个单调递减到 0 的过程不需要考虑环的入口在哪里也不用管环的长度是多少。哪怕 L 1也就是链表尾部节点自己指向自己快指针绕一圈后也会立刻追上慢指针。如果链表无环那么快指针会先在某个时刻走到 null循环自然终止。这个“先判断 fast 和 fast-next 是否为空再移动”的顺序是很多第一次写的人最容易漏掉的地方。2.2 找到入口点二次相遇的完整推导判断环存在还不够LeetCode 142 还要求返回环的入口节点。这时需要做一个稍微复杂一点的数学推导也是考研数据结构里常见的分析题。我之前一直觉得这个推导很难直到用一个具体的长度关系去画图才彻底理顺。设链表头节点到环入口的距离为 a入口到第一次相遇点的距离为 b环的剩余长度为 c那么环长 L b c。注意这里的 b 和 c 都是按节点数来算的。在第一次相遇时慢指针走了 a b 步快指针走了 a b kL 步其中 k 是快指针在环内比慢指针多走的圈数且 k ≥ 1。因为快指针速度是慢指针的 2 倍所以有时间关系2 × (slow走过的步数) fast走过的步数 2(a b) a b kL a b kL a kL - b (k - 1)L (L - b) (k - 1)L c这个式子的含义非常漂亮从链表头走到环入口的距离 a竟然等于从第一次相遇点继续往前走 c 步绕了若干圈再到达的位置——也就是环入口。换句话说如果我们让一个指针从链表头出发另一个指针从第一次相遇点出发两者都保持每次走 1 步那么它们一定会在环入口处再次相遇。这个结论给找入口节点提供了直接可用的算法ListNode *detectCycle(ListNode *head) { ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { break; } } if (fast nullptr || fast-next nullptr) { return nullptr; } slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; }2.3 编码细节与边界条件这段代码看起来不长但边界条件能绊倒不少人。我总结几个必须检查的点。第一判空链表和单节点链表。如果 head 本身为空或者 head-next 为空说明链表最多只有一个节点不可能有环直接返回 false 或 nullptr。这一步不做下面访问 head-next-next 就直接越界了。第二循环体内移动快指针时必须确保 fast 和 fast-next 都不是 null。有些写法是先判断 fast-next然后直接取 fast-next-next假如第二个节点恰好是 null就又越界了。正确做法就是在 while 条件里把 fast ! nullptr 放在前面利用 的短路求值也就是我上面代码里的写法。第三找入口时的二次循环不加任何判空。因为此时已经确认链表有环两个指针在环内和链路内移动都不会碰到 null所以可以直接 while (slow ! fast)。另一种容易错的地方是把 fast 的初始化写成了 head-next。虽然这也是合法写法但会让慢指针和快指针从一开始就错开一步后面的推导关系会变强烈建议保持两个指针都从 head 出发。判环不受影响但找入口的推导会乱套。3. 快指针步长为什么默认是 2一个被很多人忽略的选型问题3.1 相对速度视角步长 2 与步长 3 有什么区别我见过不少人在讨论里问为什么快指针一次走 2 步走 3 步行不行这个问题其实很值得认真想一下因为它涉及 Floyd 判圈算法的本质。先看相对速度。慢指针步长为 1快指针步长为 vv 1那么每一轮循环后两个指针之间的距离差减少 v - 1。当 v 2 时相对速度是 1这意味着只要两个指针都在环内它们之间的距离差会严格地按 1、2、3……依次逼近 0不会跳过“相遇”这个状态。这是步长 2 最直观的优点必然相遇且推导过程最干净。当 v 3 时相对速度是 2问题就微妙了假设两个指针在环内的初始距离差为 d如果 d 能被 2 整除那么它们会在第 d/2 轮相遇如果 d 不能被 2 整除就会在环内多绕一圈变成 d L再看能不能被整除。虽然从理论上说只要环长和相对速度互质最终也能相遇但需要的圈数不稳定而且不像 v 2 那样“一轮逼近一步”地简洁。实际上 Floyd 判圈算法对任意 v 1 都是能判环成功的但只有当 v 2 时找入口的“二次相遇”推导才最直观。步长一旦大了虽然在判环上没问题但入口推导的公式会变得很丑笔试面试时解释起来也费劲。3.2 步长太大容易出错的三件事在实际做题时把步长调大会引入三类风险。第一判空逻辑变复杂。快指针步长越大一次性向后跳的节点越多每一步都可能踩到 null代码里就要写更多防御性判断。我在刷题时曾经把快指针步长改成 3 来“验证”边界结果发现 while 循环条件多写了两层代码可读性明显下降。第二找中点的语义会变。找中点这个场景里快慢指针的“速度二倍关系”是精心设计过的快指针到末尾时慢指针正好走了一半。如果把步长改成 3那么在链表节点总数为奇数或偶数时慢指针落点的奇偶性不一致根本没法统一处理。第三时间上并不划算。虽然判环的复杂度依然是 O(n)但快指针步长越大进入环后可能要在环内多转几圈才能与慢指针相遇。尤其是那种“先有一段很长无环部分、环很短”的链表步长 2 和步长 100 的时间差距其实不大但步长 2 的实现简单得多。3.3 实际工程和考试里怎么选核心结论就是默认步长 2没有特殊情况不要改。面试或考试里也只有步长 2 才是大家公认的标准写法。有一种拓展场景值得一提就是步长差为 1 的组合用来找“两个链表的交点”时有另一种同向双指针的变体两个指针先各自遍历自己的链表走完一条就去走另一条最终会在交点相遇。这种算法虽然也用了“两个指针”但步长相同只是遍历路径交错和快慢指针的速度差思想不是一回事别混在一起背。4. 中点、倒数第 k 与回文判断快慢指针的第二梯队应用4.1 找链表中点快指针走完慢指针恰好落位环形链表只是快慢指针的入门应用找链表中点才是真正高频率、实用价值超高的场景。比如归并排序链表版LeetCode 148、回文链表判断LeetCode 234第一步几乎都是找中点。核心写法非常简单ListNode* findMiddle(ListNode* head) { if (head nullptr) { return nullptr; } ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } return slow; }注意一个细节当链表节点总数是偶数时这个写法返回的是中间两个节点中靠右的那一个。比如 1→2→3→4最终 slow 停在 3 而不是 2。如果某个题目需要返回靠左的中点就得把 while 条件改成 fast-next ! nullptr fast-next-next ! nullptr让快指针在倒数第二个节点时停住这样 slow 就会停在靠左的位置。这个差异我在面试时被问过一次很多刷题网站的标准答案也不统一。建议自己先想清楚你写的这个循环在“两个节点”的链表上返回谁在“四个节点”的链表上返回谁把这个彻底想通找中点就不会再慌了。4.2 倒数第 k 个节点快指针先出发慢指针再跟上另一种常用的变体是找倒数第 k 个节点。思路不复杂先让快指针从头节点走 k 步然后慢指针从头节点出发两个指针每次都走一步。当快指针走到链表末尾的 null 时慢指针正好停在倒数第 k 个节点上。ListNode* findKthFromEnd(ListNode* head, int k) { ListNode *fast head; ListNode *slow head; for (int i 0; i k; i) { if (fast nullptr) { return nullptr; // k 超过链表长度 } fast fast-next; } while (fast ! nullptr) { fast fast-next; slow slow-next; } return slow; }这个思路的巧妙之处在于快指针比慢指针恰好领先 k 个位置当快指针触到末尾时两者的“位置差”正好等于倒数第 k 个点的定义。它不需要先算链表长度也不需要第二次完整遍历一次循环就把位置锁定了。很多链表删除类题目会在此基础上加一个哑节点。比如 LeetCode 19 要求删除倒数第 n 个节点因为要删除节点我们必须找到它的前一个节点所以可以让快指针先走 n 步慢指针停在要删除节点的前一个节点然后用 slow-next slow-next-next 完成删除。这里加哑节点 dummy 是为了统一“删除头节点”的情况省去单独判断。4.3 回文链表找中点加反转的组合套路回文链表LeetCode 234是快慢指针、反转链表、双指针三个知识点的综合题。我先说思路再放一个能跑通的骨架代码。第一步用快慢指针找中点。第二步把中点之后的链表原地反转。第三步两个指针分别从头节点和反转后的头节点同时向后遍历逐个比较值是否相等。最后如果都相同就是回文链表。bool isPalindrome(ListNode* head) { if (head nullptr || head-next nullptr) { return true; } // 1. 找中点 ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } // 2. 反转后半段 ListNode *prev nullptr; ListNode *cur slow; while (cur ! nullptr) { ListNode *nxt cur-next; cur-next prev; prev cur; cur nxt; } // 3. 对比 ListNode *left head; ListNode *right prev; while (right ! nullptr) { if (left-val ! right-val) { return false; } left left-next; right right-next; } return true; }注意这个版本会改变原链表的结构面试时最好提一句“如果需要保持原链表不变可以再把后半段反转回来”。把这句话说出来面试官会觉得你不仅会做题还考虑到了工程上的副作用。5. 数组场景与翻车记录快慢指针不是链表专属5.1 寻找重复数把数组看成链表快慢指针的适用范围其实超出链表。LeetCode 287 这道题就是典型给定一个包含 n 1 个整数的数组每个整数在 1 到 n 之间假设只有一个重复数字要求找出它并且不能修改数组、只能用 O(1) 的额外空间。我第一次看到这题时完全没往快慢指针上想直到有人提醒我你可以把数组理解成一个链表。具体来说把数组的下标 i 当作节点把 nums[i] 当作这个节点指向的下一个节点。因为 nums[i] 的范围是 1 到 n所以这些值永远可以作为下一个下标被访问。又因为数组中有重复数字必然存在两个不同的下标指向同一个值也就是“链表”中出现了环而环的入口就是重复数字。int findDuplicate(vectorint nums) { int slow nums[0]; int fast nums[0]; do { slow nums[slow]; fast nums[nums[fast]]; } while (slow ! fast); slow nums[0]; while (slow ! fast) { slow nums[slow]; fast nums[fast]; } return slow; }这个写法本质上和链表的 detectCycle 一模一样只是把指针的 next 换成了数组取值。但它有一个容易忽略的细节不能从下标 0 出发作为“head”因为下标 0 可能不在值域里无法被别的节点指向所以要从 nums[0] 开始把它当成链表的第一个节点。5.2 原地去重一快一慢按位置写回还有一类常见的数组题目也叫“快慢指针”但和链表里的速度差完全不同——原地去重。题目一般长这样给定一个有序数组要求原地删除重复元素返回新长度。不能申请额外数组空间 O(1)。这里用两个下标慢指针 slow 表示“已去重区间的末尾位置”快指针 fast 遍历整个数组。遇到一个和当前保留值不同的元素就把它写到 slow 位置然后 slow 前进一位。int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int slow 1; for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[fast - 1]) { nums[slow] nums[fast]; } } return slow; }这个例子我想说明一点快慢指针本质上是一种“两个指针保存两个位置信息”的模板同一个名称在不同题目里的推进策略是完全不同的。链表里靠速度差制造位置差数组原地去重靠快指针探查未处理区间、慢指针标记已保留区间。别死记套路而是理解每个指针维护的是哪个信息。两类用法我放在一起对比类型指针维护的信息推进策略典型场景链表快慢指针位置差异/相遇关系速度不同判环、找中点、倒数第 k数组快慢指针已处理区间与未处理区间的边界一读一写原地去重、移除元素5.3 我实际踩过的几个典型坑前面介绍了这么多现在该说说我实际写代码时踩过的坑了。每一个都是真实发生过的错误拿出来给大家当反面教材。第一个坑循环终止条件写错导致死循环。在链表的 hasCycle 里有人会把 while 写成 while (fast-next ! nullptr fast ! nullptr)这样虽然逻辑上等价但 fast-next 在 fast 为 null 时先行访问就崩了。正确顺序是先把 fast 判空。也见过有人把 while 写成 while (slow ! fast) 然后用 break 直出结果条件少写了 else 分支直接死循环。链表题一旦出现死循环先检查快指针有没有真正更新再看循环条件有没有可能永远为真。第二个坑找中点时“前中后中”没分清。LeetCode 876 的题意是偶数节点数时返回第二个中点也就是靠右那个对应 fast fast-next 的写法。但有些题需要靠左的中点比如平衡二叉树转链表之类的场景就要改循环条件。我一开始没注意导致 148 归并排序链表时把链表切错了左右子链表长度不一致排序结果全乱。第三个坑快指针更新写成了 slow 的更新。这个听起来离谱但真的发生过——Copy 了一段代码把 fast fast-next-next 改成了 fast slow-next结果一个指针原地打转判环直接超时。在在线评测平台上一旦时间超限先把两个指针的更新语句逐行核对一遍很多低级 bug 就能立刻暴露。第四个坑数组版本的入口值。找重复数那题我一开始写成 int slow 0; int fast 0;结果下标 0 上的值不一定能作为合法入口整个指针链一开始就走错了。后来改成从 nums[0] 开始一切正常。6. 备考点睛与延伸快慢指针在双指针家族中的位置6.1 快慢指针和对撞指针、滑动窗口怎么区分很多人把“双指针”当成一个笼统的算法其实内部还分好几个流派。如果分不清做题时很容易用错。我按自己的理解做个区分对撞指针两个指针从两端向中间移动适合有序数组、前缀和、回文串这类问题常见的是两数之和 II、反转字符串等。滑动窗口两个同向指针夹住一段连续区间窗口大小可变或固定适合最长子串、最小覆盖子串这类“连续区间”问题。快慢指针两个同向指针靠速度差或延迟启动来制造位置差适合链表里需要找位置、找某次“相遇”的场景。三者在实现上都是两个指针但信息模型完全不同。对撞指针用端点信息夹出目标滑动窗口维护的是区间和/区间状态快慢指针维护的是两个指针的相对位置关系。我建议做题前先问自己一句需要的信息是靠两端逼近、连续区间还是靠相对位移想清楚再动手基本就不会用错。6.2 拿到链表题后的思考路径和刷题清单链表题里遇到环、中点、倒数位置这些关键词快慢指针应该立刻出现在脑子里。但怎么快速判断一个题能不能用快慢指针我的经验是三步走。第一步看空间限制是否要求 O(1)如果是哈希表方案直接淘汰。第二步看问题是否涉及“相对位置”“相遇”“环”这类概念只要涉及快慢指针就可能是解法。第三步看是否需要一次遍历完成如果题目明确要求只能遍历链表一次快慢指针往往是标准解。这里给一个我刷题下来的最小清单按顺序做基本能覆盖快慢指针的所有典型考法题目考察点建议LeetCode 141 环形链表判环入门第一题把迭代过程画一遍LeetCode 142 环形链表 II找环入口手动推导 a (k-1)L c别背代码LeetCode 876 链表的中间节点找中点注意返回靠左还是靠右LeetCode 19 删除链表的倒数第 N 个节点倒数位置加哑节点练习 dummy 节点的使用LeetCode 234 回文链表找中点加反转三步组合最考验综合能力LeetCode 287 寻找重复数数组上的快慢指针理解“下标即节点”的映射关系LeetCode 202 快乐数快慢指针变体用数字替换代替指针移动理解环的意义快乐数那题顺便说一句它把每个数字下一步的“节点”定义为各位平方和。如果最终能到 1就相当于链表走到了 null如果进入循环就相当于出现了环。用快慢指针判环就能在不额外开哈希表的情况下判断是否快乐数。我第一次写这题时也是一愣这不就是链表题的套壳吗。6.3 一点个人的备考经验写在最后想分享一个我自己的习惯。刚学快慢指针的时候我总觉得自己懂了推导但过两天再写又卡壳。后来我直接把 142 题的推导过程写在一张便签上贴在显示器边两次相遇、步长二倍、a 等于 (k-1)L 加 c、同速再相遇即入口。每次写链表题之前瞄一眼慢慢就形成条件反射了。还有一个验证方法帮了我大忙写完任意一个快慢指针相关算法立刻用这五组测试数据跑一遍——空链表、单节点链表、无环的偶数长度链表、无环的奇数长度链表、环入口在头部或尾部的链表。这五组覆盖了绝大多数边界情况跑完基本心里就有底了。我后来发现面试时如果候选人能主动说出“让我先跑一下边界测试”面试官对他的印象分通常会明显上升。链表类题目的核心从来不在代码量而在于你能不能把指针的移动过程在脑子里“播放”出来。快慢指针的技巧本身不难难的是理解每一次移动之后两个指针的位置关系到底变化了多少。建议所有准备考研数据结构或算法面试的朋友找张纸把环形链表那题的推导过程亲手写一遍写完了再回来写代码你会发现自己对这些题的理解会上一个台阶。这也是我写这篇系列第十五篇时最想传递的东西。