今天是我用C刷LeetCode打卡的第十天进度条走到LinkedList这块也积累了不少题。今天想聊的是这几天出镜率最高、也是很多人“一看就会、一写就废”的经典套路快慢指针。快慢指针本质上就是让两个指针以不同速度在链表或数组上移动一个每次走一步一个每次走两步。它最擅长解决三类问题判断链表是否有环、寻找链表中点或倒数第K个位置、以及在数组里找重复元素。如果你正在准备C相关的技术面试这个知识点几乎绕不开十次面试里至少有两三次会碰到它的变形题。这篇把判环的数学推导、找中点的边界处理、数组映射的思路以及我踩过的几个坑一并写清楚适合还在链表题里挣扎的刷题党也适合面试前想快速温习套路的人。1. 先搞清楚快慢指针到底是啥1.1 一个生活化的理解方式快慢指针听起来玄乎其实是小学追及问题的翻版。想象两个人同时出发一个每秒跑两米一个每秒跑一米。要是直线跑道快的永远在前面两人永远不会碰面可要是环形跑道快的人跑一圈之后总会从后面追上慢的。这个“追上一圈”就是快慢指针的全部秘密。链表里存在环快指针绕一圈回来就能撞上慢指针链表没有环快指针会先踩到链表末尾的空指针慢指针这时候顶多走到一半。一次遍历既解决了“有没有环”的问题还顺手把“中间位置”也算出来了。我特别建议用“两个速度不同的指针”这个思路去理解而不要死背代码模板。快慢指针的变体实在太多了有的让快指针先走K步有的让快慢指针不同步出发有的根本不是链表而是数组。只要抓住“谁快谁慢、谁先出发、在什么条件下相遇”这几个变量所有变体都能归到同一套逻辑下。1.2 哪些题该想到快慢指针根据我这十天的刷题体感具备下面任意两个特征的题基本都可以往快慢指针方向想数据结构是单向链表或者能通过下标映射看成链表。求的是环、中点、倒数第K个位置这类“位置关系”。题目明确要求空间复杂度O(1)不能用哈希表记录访问过的节点。存在两个序列之间的追赶关系一个前进速度快一个前进速度慢。反过来也要提醒一句如果题目要你合并两个有序链表、找两个链表的交点、或者做排序那就不是快慢指针的主场。我刚开始刷的时候吃过亏看到linked开头就硬套快慢指针最后代码写得又长又绕。后来我养成了先判断题型再选工具的习惯效率一下子高了不少。1.3 为什么不用哈希表很多人看到“判断链表有没有环”或者“找数组里的重复数”第一反应是哈希表把访问过的节点地址或数组下标存进unordered_set每次走到新位置就查一下之前见没见过。这个思路本身没问题代码甚至更短但它有两个明显的代价。一是空间复杂度。哈希表最坏情况下要存下所有节点的地址空间消耗是O(n)一旦面试官追问“能不能优化到O(1)空间”这个方案就站不住了。二是哈希表本身的性能损耗。unordered_set平均查询确实是O(1)但大量哈希冲突和扩容发生时实际耗时比快慢指针多不少。我并不是说哈希表解法不行它依然是完全正确的思路而且可读性很好。但在这类题目里“要求O(1)空间”几乎就是明着告诉你别用哈希表。能第一时间识别出这个信号说明你对这个套路已经有感觉了。2. 核心套路判环与找环入口2.1 141. 环形链表判环模板141题是快慢指针的入门题需求很简单给一个链表头指针判断链表里有没有环。最直接的想法是用哈希表记录访问过的节点地址某个地址出现第二次就说明有环。这个解法能过但空间复杂度是O(n)。快慢指针可以把它压到O(1)空间。class Solution { public: bool hasCycle(ListNode *head) { ListNode *slow head; ListNode *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { return true; } } return false; } };这个模板有两个细节需要留意。循环条件是fast fast-next这两个判断必须都写顺序也不能换。如果fast已经走到链表末尾你还去访问fast-next就是对空指针解引用直接崩溃。当head为空或者链表只有一个节点时循环一次都不会执行函数返回false行为也是正确的。我第一次写这题犯过一个低级错误只判断了fast没判断fast-next结果遇到长度为1的链表直接段错误。后来总结了一个口诀快指针每走一步之前都要确认下一步的落点是存在的。2.2 142. 环形链表 II入口位置的数学推导141只问有没有环142要求返回环的入口节点。很多人能靠记忆写出代码但被问“为什么这样能走到入口”就卡住了。这里把推导完整写一遍。设链表头到环入口的距离为a入口到第一次相遇点的距离为b相遇点继续走回入口的距离为c。那么环的长度L b c。慢指针走了a b步快指针走了a b nL步n是快指针在环内多跑的圈数。由于快指针速度是慢指针的两倍所以2(ab) abnL整理后得到ab nL。把这个等式稍微变形a nL - b (n-1)L c。它的含义很巧妙从链表头走到环入口的距离a恰好等于从相遇点继续走c步再绕n-1圈后到达环入口的距离。于是解法就是第一次相遇后把slow挪回链表头然后让slow和fast都改成每次走一步再次相遇的地方就是环入口。class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow head; ListNode *fast head; bool hasCycle false; while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { hasCycle true; break; } } if (!hasCycle) return nullptr; slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; } };这个数学推导是面试官最喜欢深挖的点。建议你在准备的时候老老实实画一张图把a、b、c标出来自己推一遍等式。能讲清楚推导过程的人和只背得住代码的人在面试官眼里完全是两个档次。3. 链表位置题中点和倒数第K个节点3.1 876. 链表的中间结点找链表的中间节点最笨的办法是先遍历一遍拿到链表长度再走一半。思路简单但要两趟遍历。快慢指针可以一趟搞定fast每次走两步slow每次走一步等fast抵达链表末端时slow正好停在中间位置。class Solution { public: ListNode* middleNode(ListNode* head) { ListNode *slow head; ListNode *fast head; while (fast fast-next) { slow slow-next; fast fast-next-next; } return slow; } };这里有一个边界细节容易忽略当链表节点数是偶数时LeetCode要求返回第二个中间节点。比如1-2-3-4要返回3而不是2。上面的代码跑完后slow指向的就是第二个中间节点正好符合题意。如果你遇到需要返回第一个中间节点的场景可以额外用一个prev指针记录slow的前一个节点或者通过调整循环终止条件来实现。这道题单独出现时很基础但它在真实面试里更多是作为综合题的一个零件。比如判断回文链表先用快慢指针找中点再反转后半段最后逐节点比较。中点这一步如果写得不稳后面全部跟着出错。3.2 倒数第K个节点先走K步再同步走“只遍历一次找到倒数第K个节点”是快慢指针的另一个经典变体。做法是让fast先走K步然后slow和fast同步前进。当fast走到链表末尾的nullptr时slow与末尾之间恰好隔了K个节点此时slow指的就是倒数第K个节点。class Solution { public: ListNode* getKthFromEnd(ListNode* head, int k) { ListNode *slow head; ListNode *fast head; for (int i 0; i k; i) { fast fast-next; } while (fast) { slow slow-next; fast fast-next; } return slow; } };这个模板的坑主要在K的语义上。K一般从1开始计数倒数第1个是末尾节点。如果题目给的K从0开始循环次数要相应调整。另外如果K大于链表长度上面的代码在for循环里就会把fast走到nullptr继续操作会出问题。实际面试时最好先和面试官确认输入保证或者自己加一个越界判断。和它强相关的一道题是LeetCode 19删除链表的倒数第N个结点。这道题在找目标节点的同时还要把它删掉而删除操作需要拿到目标节点的前驱所以做法变成fast先走N步然后两个指针同步走fast到末尾时slow恰好指向目标节点的前驱再执行slow-next slow-next-next。这里还要注意头节点可能被删除的情况通常用虚拟头节点来简化处理。3.3 虚拟头节点的小技巧在做删除类操作时我几乎总是配合虚拟头节点使用。直接操作原始链表时如果要删除的是头节点因为它没有前驱就得单独写一个if分支非常啰嗦。new一个dummy节点让dummy-next head所有节点就都有了统一的前驱。ListNode* dummy new ListNode(0); dummy-next head; ListNode *slow dummy; ListNode *fast dummy; for (int i 0; i n; i) { fast fast-next; } while (fast) { slow slow-next; fast fast-next; } slow-next slow-next-next; return dummy-next;这里fast先走的步数是n1而不是n因为我们要找的是倒数第N个节点的前驱。fast先走n1步然后跟slow一起走等fast到末尾时slow恰好停在目标节点的前一个位置。这个思路配合快慢指针用起来非常顺手凡是“给你头节点要你修改或删除链表中的节点”的题我都建议优先考虑虚拟头节点。4. 把快慢指针用到数组里4.1 287. 寻找重复数快慢指针不只是链表专属。LeetCode 287寻找重复数是它在数组里的经典应用给定一个包含n1个整数的数组每个数字都在1到n之间只有一个数字会重复出现要求不能修改数组只能用O(1)的额外空间。如果第一次见这道题很容易想到排序、哈希表或者求和做差但这几个方案要么改了原数组要么超了空间限制。快慢指针的思路是把数组看成一个隐式链表从下标i出发下一步走到nums[i]。因为数组值都在1到n之间而下标范围是0到n所以这个“走下一步”的过程永远不会越界。又因为存在重复数字必然有两个不同下标指向同一个值这就在隐式链表里形成了一个环。环的入口恰好就是重复的那个数。class Solution { public: int findDuplicate(vectorint nums) { int slow nums[0]; int fast nums[nums[0]]; while (slow ! fast) { slow nums[slow]; fast nums[nums[fast]]; } slow 0; while (slow ! fast) { slow nums[slow]; fast nums[fast]; } return slow; } };注意初始化的写法slow从nums[0]出发fast一次走两步也就是先走到nums[0]再走到nums[nums[0]]。这一步跟链表写法完全对应链表里fast fast-next-next在数组里就是fast nums[nums[fast]]。4.2 数组当链表的边界条件把数组当链表走最容易踩的坑是数组值和下标的关系。LeetCode 287的值域是1到n下标是0到n因此从任意位置出发下一步的下标一定大于等于1不会回到0这就保证了“环的入口”绝对不是0。这也是为什么最后把slow重置为0之后两个指针一起走反而能在重复数字处相遇。另一个坑是不要试图用“值相等”来判断重复。在隐式链表里同一个值可能被多个不同的下标映射到而你真正要找的是那个被重复映射的值。第一次循环判环时快慢指针比较的是位置而不是值大小这个区别最好写进注释里不然代码review时别人很容易看懵。这类题的共同套路就是用索引当指针用数组值当next。一旦适应了这种映射思维后续再遇到类似题目就会觉得很有规律。我把链表快慢指针和数组快慢指针放在一起对比着学效率比单独刷高很多。5. C实现里最容易翻车的几个细节5.1 循环条件与空指针判断先说链表快慢指针的经典循环条件while (fast fast-next)。这两个判断缺一不可。如果只写while (fast)遇到偶数长度链表时快指针最后一次移动需要访问fast-next-next而fast-next可能已经是空指针妥妥的段错误。如果只写while (fast-next)当head本身就是空时第一次判断就会对空指针解引用。两个条件的书写顺序也有讲究。C的是短路求值当fast为false时根本不会去执行后面的fast-next所以把fast写在前面是安全的。一旦调换顺序当fast为空时会先对空指针解引用照样崩溃。我调试时见过这个错误好几次崩溃现场完全看不出来打印链表数据也正常最后才发现是循环条件顺序反了。判断空指针时我用的是nullptr而不是NULL。前者有明确的类型能参与重载决议在C11及以后的标准里是首选。LeetCode的环境默认支持C11以上直接写nullptr就好不用考虑兼容老标准。5.2 nullptr、内存与本地调试C在LeetCode上做链表题节点指针默认是裸指针。有的同学习惯用shared_ptr管理节点这在本地小项目里没问题但在评测环境里链表的创建和释放都由框架控制你只需要用原始指针解题。自己new出来的测试链表退出前记得手动delete虽然LeetCode判题环境不管这些但本地一直跑内存泄漏还是很难受。本地调试我用的方案是在VSCode里配好C编译环境装上C/C扩展和调试器然后在关键位置打断点查看指针地址。排查链表环问题时有个小技巧不要只看节点值要打印节点地址。环里可能存在重复的值但地址一定是唯一的。如果发现两个指针的地址在循环若干次后相同就说明确实进环了。再分享一个本地验证的方法写一个工具函数限制最多打印20个节点防止有环链表把控制台刷爆。我早期调试环形链表时手滑写了一个没有终止条件的打印循环终端直接卡死后来给所有链表打印函数都强制加上了计数上限。5.3 复杂度与性能对比快慢指针类题目绝大多数都能做到时间复杂度O(n)、空间复杂度O(1)。这里单独提一下复杂度因为很多人会把快慢指针和二分法搞混觉得快指针跑得快时间复杂度会更优。实际上并不会。快指针虽然每次走两步但总步数依然和链表长度成线性关系。无环链表快指针最多走n/2次循环就到达末尾每次循环做常数次操作所以是O(n)。有环链表快指针追上慢指针之前也最多走O(n)步不会因为环的重叠变成O(n方)。真正拉开差距的是空间复杂度。哈希表最坏需要O(n)空间快慢指针只用两个指针变量恒为O(1)。在内存敏感的系统级C岗位上面试官往往特别看重这一点这也是快慢指针在C面试题库里高频出现的原因。6. 这个知识点的后续扩展6.1 值得继续刷的变体题如果你已经把142、876、287这几道题都写顺了我建议按下面的顺序继续加深删除链表的倒数第N个结点快慢指针配合虚拟头节点的典型场景。回文链表找中点加反转后半段一道题复习两个重点。快乐数把每个数的各位平方和当成下一个节点用快慢指针判环。重排链表找中点、反转、合并三步走综合性强。环形数组是否存在循环偏竞赛适合时间充裕时挑战。这几道题难度递增但核心都离不开今天反复强调的“一快一慢谁先到谁就是关键”。尤其是202和457它们看起来跟链表毫不相关依然能用快慢指针解决。这就是我前面反复讲“理解原理而不是背代码”的原因。6.2 我的刷题节奏建议我给自己定的节奏是每个知识点先做两三道经典题把模板吃透再做两三道变体题验证自己是不是真的理解了。快慢指针这个专题我用三天刷完了141、142、876、19、234、287每天控制在两小时左右感觉比之前一天刷十道但全部遗忘要扎实得多。最后再分享一个心得。快慢指针这类题写代码只是最后一步更重要的是前面的推导和画图。142和287我第一次做的时候代码很快就写完了但被追问“为什么这样能找到入口”时愣了几秒说不出所以然。后来我强迫自己把每一步指针的位置画在纸上把等式推导完整再遇到同类问题就顺畅多了。希望你也能少走这个弯路。