如果你刷过牛客的高频题单或者在 LeetCode 上把链表题按热度排过序K 个一组翻转链表大概率就躺在“必刷”那一栏。这道题编号 25标签是链表、递归、双指针难度标了 Hard但真正动手做过的同学都知道它的算法思想并不复杂——难的是你把指针写对、把边界条件理顺。面试官爱出这道题是因为它能用十分钟看出你到底是真的写过链表题还是只背过模板。先说一个反直觉的点K1 时链表完全不变K 等于链表总长度时就是整条链表全反转所以这道题本质上是“反转链表”和“反转链表 II”的组合升级。这篇我按自己面试和辅导别人的经验把这题的思路、两套主流写法、踩坑点一次讲清楚。适合正在准备算法面试、或者刷题刷到链表专题想一口气吃透反转类题目的同学。就算你现在只会遍历链表读完也能照着把代码写出来。1. 题目理解与面试定位1.1 题干到底在说什么题目要求一句话总结把链表按每 K 个节点分成一组组内做反转组与组之间的相对顺序不变最后如果剩余节点不足 K 个保持原样不动。举个例子链表1-2-3-4-5当 K2 时结果是2-1-4-3-5。当 K3 时结果是3-2-1-4-5。第二个例子很多人会错因为末尾的4-5只有两个节点不足 K3所以不翻转保持原顺序接在后面。这里有两个约束缺一不可一是“组内反转”二是“末尾不足一组不反转”。很多人在 LeetCode 上提交报错不是反转逻辑写错而是第二点没处理好把最后那截不够长度的也翻了。面试里如果犯这种错比写不出代码更减分因为说明你没有把题目条件读完整。1.2 这道题在面试里的地位你可能会问链表题那么多为什么偏偏这道题是高频考点我自己的体会是这题考察的面非常全它需要你维护多个指针并且保证每一步都不丢节点它需要虚拟头节点的技巧否则头节点翻转后无法返回新头它需要先遍历统计长度或者在高潮处判断剩余节点是否够一组它还需要你在纸上把指针画清楚靠纯脑补很容易翻车。所以面试官只要看你写这题的过程基本就能判断你的链表基本功属于什么水平。背过答案的人写起来磕磕绊绊指针变量一多就开始乱真正做过的人会先画图、再说思路、再动手整个过程有条不紊。另外这道题和 LeetCode 24两两交换链表中的节点、LeetCode 92反转链表 II之间是强关联。面试官经常会把这题作为基础题然后现场改成“只反转第 m 到第 n 段”或者“K2 怎么优化”。一道题能不能举一反三往往比题目本身 AC 不 AC 更重要。2. 思路拆解两套核心方案2.1 为什么要用虚拟头节点链表反转类问题第一个要养成的习惯就是构造一个虚拟头节点 让反转后的新头有地方挂。你可以想象一下链表1-2-3-4K4翻转后变成4-3-2-1原来的头节点 1 变成了新链表的尾节点。如果你一开始只持有head指针翻转完成后这个指针指向的节点已经变了位置你怎么拿到新头你当然可以用一个变量专门记录新头但这样逻辑上要多开一个分支代码也容易乱。虚拟头节点的做法是不管链表怎么翻转dummy-next永远指向新链表的头节点最后直接return dummy-next就行。这就像系鞋带的时候先打一个活结后面怎么拉都不会把鞋带拉散。2.2 迭代头插法面试首选的完整思路迭代方案里最推荐的是“头插法”因为它只涉及指针的交换不需要额外的数组空间。思路分四步先遍历一遍链表统计总长度len只要len K说明还能凑出一组可翻转的区间在组内执行K-1次头插把后面的节点依次挪到组的最前面一组处理完后把前置指针pre移动到这一组的末尾同时len - K继续下一组。很多人不理解为什么是 K-1 次而不是 K 次。这里解释一下当一组待翻转的节点是1-2-3时节点 1 最终会变成这一组的最后一个节点它不需要再往前插真正需要插到前面的只有 2 和 3 两个节点。每次头插都会让其中一个节点变成组内第一个节点。所以 K 个节点需要 K-1 次头插。每次头插的细节是先把当前节点cur的下一个节点存为nxt然后把cur-next直接跨过nxt指向后面再把nxt插到pre-next的位置。这个过程中cur一直指向组内第一个节点同时也是翻转后组内的最后一个节点它从头到尾没有移动过所有被插过来的新节点都插在它前面。一组结束后cur自然就是这一组的末尾下一组的pre就是它。2.3 递归法思路优雅但容易绕晕的方案递归的思路更直观一些每一层只处理一组 K 个节点剩下的交给函数自己处理。具体来说从头节点开始往后走 K 步得到第 K1 个节点如果不足 K 步说明当前不够一组直接返回头节点如果够 K 个节点先递归处理第 K1 个节点之后的链表拿到后面处理完的新头翻转当前这 K 个节点把翻转后的尾节点接到递归返回的结果上。递归代码写出来比迭代短很多但有一个代价递归深度是n/K如果链表特别长会占用额外栈空间。面试时如果追问空间复杂度迭代版可以理直气壮地说 O(1)递归版得老实承认 O(n/K)。另外递归版有个容易搞混的点翻转完当前组后返回的新头是组内原来的最后一个节点而不是当前层的head。很多人在这一步绕进去所以我建议面试时优先写迭代法递归法作为思路扩展讲给面试官听。3. 手撕代码与核心细节3.1 迭代法完整实现C先上可以直接用的 C 代码注释我写得比较细/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { // 虚拟头节点统一处理头节点变化的情况 ListNode* dummy new ListNode(0); dummy-next head; ListNode* pre dummy; ListNode* cur head; // 第一遍遍历统计链表长度 int len 0; ListNode* p head; while (p ! nullptr) { len; p p-next; } // 只要剩余节点还够一组就继续处理 while (len k) { cur pre-next; // 当前组的第一个节点 // 头插 k-1 次把后面的节点依次插到 pre 后面 for (int i 1; i k; i) { ListNode* nxt cur-next; // 保存要移动的节点 cur-next nxt-next; // 跨过 nxt先把链表连好 nxt-next pre-next; // nxt 指向组内第一个节点 pre-next nxt; // 把 nxt 插到 pre 后面 } pre cur; // 当前组的最后一个节点成为下一组的前驱 len - k; // 减去已处理的一组 } return dummy-next; } };逐行说几个关键点。dummy和pre的关系pre永远指向当前待处理组的前一个节点。第一组的前驱就是dummy所以头节点被反转后也能顺利接回来。cur pre-next这行不要省略或挪位置。很多人写的时候喜欢在循环外用变量一直记录cur但每组开始前重新从pre-next取当前组第一个节点能避免上一组结束后的指针错位问题。内层循环里nxt cur-next一定要先保存。头插法最容易犯的错就是先改了cur-next然后发现原来的下一个节点找不到了。pre cur这个赋值也值得说一下一组处理完后cur指向的是这一组最初的第一个节点现在它因为一直被“往后面顶”已经变成了这一组的最后一个节点所以它天然就是下一组的前驱。这个性质很优雅不需要额外去数位置。3.2 递归法完整实现与对比递归版代码长这样class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode* cur head; int count 0; // 走 k 步看看够不够一组 while (cur ! nullptr count k) { cur cur-next; count; } // 不够 k 个保持原样 if (count k) { return head; } // 够 k 个先递归处理后面的链表 ListNode* newHead reverseKGroup(cur, k); // 翻转当前 k 个节点 while (count-- 0) { ListNode* tmp head-next; head-next newHead; newHead head; head tmp; } return newHead; } };这段代码里最绕的是最后的while (count-- 0)翻转过程。如果你看不太懂可以把它想象成“一个一个摘下来头插到新链表上”tmp head-next先把后面的节点缓存起来head-next newHead让当前节点指向已翻转好的部分newHead head更新“新链表头”为当前节点head tmp继续处理下一个节点。这样循环 K 次就能把当前组的 K 个节点彻底反过来并且接上后续部分。两个版本对比的话我个人的建议是面试写迭代交流讲递归。迭代法代码量稍多但每一步都看得见摸得着递归法代码简短但对思维要求高而且空间复杂度不如迭代。如果你递归基础一般不建议现场挑战这个写法写岔了比迭代更难排查。3.3 复杂度分析与 Java/Python 实现说明复杂度方面时间复杂度O(n)每个节点被遍历常数次。第一遍统计长度遍历一次后续翻转时每个节点最多被访问两次一次保存一次移动整体线性。空间复杂度迭代版 O(1)只用到了几个指针变量递归版 O(n/K)因为每一层递归要保存当前栈帧。如果你用的是 Java逻辑和 C 完全一样只是把ListNode*换成ListNode引用类型天然就是“指针”的效果。需要注意的点是Java 里没有手动释放内存的问题但你要避免无意中把pre和cur指向同一个对象导致链表成环。Python 同理定义节点类之后操作 next 的规则完全一致。很多同学面试时用 C 写链表题写完忘了delete dummy这个看面试官习惯有的会提一句内存管理。我的建议是面试场合以代码可读性为先主动说明“这里如果考虑内存释放还需要 delete 虚拟头节点”比真的去 delete 更有加分感因为面试官知道你有这个意识。4. 边界测试与易错点排查4.1 必测的几组用例写完之后不要急着交先在脑子里跑一遍测试用例。我整理了一份我刷这题时常用的用例清单你可以直接抄用例输入期望输出说明空链表[]k2[]任何代码都不能崩单节点[1]k1[1]k1 是最平凡的情况不足一组[1,2]k3[1,2]尾组不足保持原序K 等于长度[1,2,3]k3[3,2,1]相当于整表反转常规多组[1,2,3,4,5]k2[2,1,4,3,5]最常见的场景尾组不足[1,2,3,4,5]k3[3,2,1,4,5]最容易错的场景你可能会觉得这些都是废话但我在带人刷题时真见过有人把空链表测漏结果返回了dummy节点本身而不是nullptr的。虚拟头节点是new出来的一块内存不是dummy-next最后返回错了检查半天。4.2 高频 bug 现场还原这里把我在实际调试中见过最多的问题集中列一下Bug 1没统计长度最后一组不足 K 也被反转。这是最典型的问题。解决办法就是先遍历一遍拿到len每次处理完len - k用while (len k)控制循环。另一种写法是在每组开始前尝试走 K 步走不到就 break也可以但我觉得先统计长度的写法循环条件更清晰。Bug 2头插顺序写错导致丢节点。正确顺序是先存nxt再改cur-next再改nxt-next最后改pre-next。有同学先改了pre-next结果nxt-next指向的pre-next已经变成了nxt链表当场成环。记住一个口诀先摘下来再接前后最后挂上去。Bug 3忘了更新pre指针导致死循环。如果一组处理完不执行pre cur下一组的头插就会把节点插到上一组里链表越排越乱最后死循环。你如果调试时发现链表长度完全没减少多半就是这个原因。Bug 4return head而不是return dummy-next。链表一旦发生翻转原来的head就不再是新头了。这是虚拟头节点使用中最经典的误区。看到这里你可以自查一下是不是总在最后下意识返回 head。Bug 5递归版里count被 while 改了后面想再用它做别的事。递归版的count在翻转循环里会递减到 0如果你之后还拿它做判断就会被坑。所以递归版里要么用局部变量把 K 的值先存起来要么就别在翻转之后依赖 count。4.3 和相似题目的关系这题刷完之后我建议你顺手把下面三道题一起刷了因为它们的解法几乎就是从这题变形出来的LeetCode 206 反转链表。整条链表反转等价于本题 K链表长度时的特例。LeetCode 92 反转链表 II。固定区间反转核心是利用虚拟头节点找到区间前驱再对区间内做头插。LeetCode 24 两两交换链表中的节点。就是本题 K2 时的特例。你可以把本文的迭代代码里k换成 2代码照样能跑只是两两交换有更简洁的写法。把它们放在一起刷你会发现一个规律链表反转类的题本质上就是“找到区间 - 头插法翻转 - 重接边界”这三板斧。掌握这三板斧比单独背一道题的答案有用得多。5. 面试现场思路展示与变化题5.1 建议在现场如何表达思路面试和做题不一样光写出代码不够你还要让面试官看到你的思考过程。我建议拿到题之后先跟面试官说这样几句话“我先遍历一遍链表拿到总长度这样就能知道一共需要处理几组。然后我用一个虚拟头节点来统一处理头节点变化的情况。每一组内部我用头插法做翻转组内头插 K-1 次处理完把 pre 移到组尾继续下一组。最后剩余不足 K 个的节点保持原序不动直接返回虚拟头节点的 next。”这段话既交代了方案又点出了边界条件面试官一听就知道你不是在边写边猜。如果你直接闷头开始敲代码即使最后 AC 了印象分也会打折扣。面试官接下来大概率会追问几个问题这里预判一下为什么要先统计长度答为了保证最后一组不足 K 个时不翻转同时让主循环条件更清晰。空间复杂度是多少答迭代版 O(1)只用了常数个指针。如果 K 非常大接近链表长度会怎样答最多只会处理一组时间复杂度依然是 O(n)。5.2 怎么写代码能一次过在面试那种紧张环境下想一遍把代码写对有几个实操技巧第一先在白板上把链表画出来。画一个1-2-3-4-5K3 的例子手动模拟两次头插写代码时照着图来而不是凭空想。第二变量名要有区分度。我用pre表示前驱cur表示当前组的第一个节点nxt表示要移动的下一个节点。名字清晰思路就清晰一半。见过有人写a、b、c、d写到最后自己都分不清谁是谁。第三写完之后用一个小例子在代码里“走一遍”。不需要真的调试沿着循环把指针一步步标出来确认三次循环后链表形态正确再提交或交给面试官。第四注意代码风格。循环里的变量声明尽量靠近使用处不要一上来把一堆指针全部声明好这会让代码读起来很难受。5.3 变化题与延伸练习这题最常见的变体就是前面提到的 K2 和区间反转这里再说几个进阶方向供已经能 AC 的同学查漏补缺如果题目改成“最后一组也要翻转”代码只需要把循环条件从len k改成计数到组数为止或者递归时不足 K 也照单反转。如果考察双向链表核心思路不变但要额外维护prev指针头插时同步更新四个方向的引用难度会高一个台阶。如果要求“输出每组翻转后的链表中间值”就需要把本题和快慢指针结合这种跨知识点组合题也是大厂面试喜欢玩的花样。练习顺序我建议这么安排先裸写本题再改 K2 看代码能不能简化再去做 92 题区间反转最后试一下递归版。这个顺序是从具体到抽象等你能用自己的话把四种变体都讲明白链表反转这个专题基本就过关了。我记得带过的一位同学最初看这题答案都看不懂后来按“画图 - 模拟 - 复写 - 总结”这四步练了三天再遇到 92 题十分钟就写出来了。可见这个专题的特点就是想通一次全部贯通。最后再分享一个个人习惯。我刷这题时会在草稿纸上把“头插法”的每一步用箭头画三遍第一遍照着题解画第二遍遮住题解自己画第三遍把文字描述换成口头表达讲给自己听。三遍过后这个解法基本就长在脑子里了。你可以试试这比刷十遍相同题目管用。