力扣Hot 100第31题K个一组翻转链表。这道题我前前后后刷了三遍每次以为自己懂了过两个月再写一次还是会在边界条件上翻车。后来我才发现这道题根本不是在考你会不会翻转链表而是在考你有没有把链表操作里最要命的三个东西想清楚指针断链、递归边界、以及迭代时哨兵节点怎么用。如果你已经在刷Hot 100大概率不是第一次碰链表反转了。第206题反转链表是入门第92题反转链表II是进阶到这一题就是综合大考把链表按K个一组切段每段内部反转段与段之间还要接上最后不足K个的部分保持原样。逻辑不复杂但写出来到处都是坑。今天就把我在这道题上踩过的所有坑连同可以直接抄的完整代码一起写出来希望能帮你少走弯路。1. 题目拆解先搞懂“K个一组翻转链表”到底在考什么1.1 题目原意与输入输出形态题目描述很简洁给你一个链表每K个节点一组进行翻转返回修改后的链表。K是一个正整数它的值小于或等于链表的长度。如果节点总数不是K的整数倍那么最后剩余的节点应该保持原有顺序。给你举个例子。链表是1 - 2 - 3 - 4 - 5K等于2翻转后应该得到2 - 1 - 4 - 3 - 5。如果K等于3翻转后应该得到3 - 2 - 1 - 4 - 5。最后剩下的两个节点4和5不足一组保持原顺序不动。这道题的核心操作可以拆成三层第一层把整条链表切成多段每段正好K个节点。第二层对每一段内部做完整的链表反转。第三层把反转后的每一段重新拼接起来并且处理好段与段之间的连接关系。很多朋友一上来就想着把所有节点一次性处理完结果绕进去出不来。其实正确的姿势是先切段再反转最后拼接三步分开想逻辑就清晰了。1.2 这道题为什么是Hot 100里的分水岭Hot 100里链表题不少但这道题的位置非常特殊。它排在链表系列的中间偏后阶段很多刷题人走到这里会明显感到吃力。原因很简单它同时考察了递归思想、指针操作、边界处理和模块化拆解能力。你可能会说反转链表我也会递归我也会怎么合在一起就写不出来了问题出在“组合”上。反转链表只需要维护两个指针但这里你还要维护“当前组的头尾”“下一组的起点”“上一组拼接的位置”变量一多脑子就乱。而且这道题在面试里属于高频题。我印象里至少有三次模拟面试和真实面试遇到它面试官通常不会只满足于你写出一种解法他还会追问递归的空间复杂度是多少能不能改成迭代如果K等于1怎么办链表长度刚好是K的倍数怎么办这些追问才是拉开差距的地方。1.3 刷这道题之前你需要先掌握的基础如果你之前没怎么碰过链表我建议先花半小时把下面几个基础操作练熟不然直接上这题会很痛苦链表的遍历用cur cur-next走完整个链表。单链表反转用三指针prev/cur/next迭代反转或者用递归反转。哨兵节点在头节点前面加一个虚拟节点用来统一处理头节点变化的场景。递归的返回值语义想清楚每一层递归返回的到底是哪个节点。其中“返回值语义”是最容易懵的。很多人在写递归链表题时根本不知道自己 return 出去的是什么只会照着模板套一旦题目变形就报废。等下在实现部分我会专门展开讲。2. 核心思路递归分组 局部反转的设计逻辑2.1 为什么先考虑递归而不是纯迭代我第一次做这道题时第一反应是用迭代硬刚用一个外层循环遍历链表每K个切一段反转再接回去。结果写出来一坨代码变量命名都是p1 p2 p3跑起来一堆边界错误调了半天心态爆炸。后来换了递归思路一下子清爽很多。递归想问题的模式是我只管当前这一组怎么处理剩下的交给函数自己。你不用在一层逻辑里同时操心“上一组怎么接”“下一组怎么找”“全部反转完怎么收尾”只需要定义清楚一件事当前这K个节点怎么翻转翻转后返回什么然后让函数对剩余链表重复同样的操作。用递归还有个额外的好处代码读起来特别像题目的文字描述。“每K个一组翻转链表”这句话翻译成递归就是先反转前K个然后对剩下的链表递归调用同一个函数再把两部分接起来。这样代码和思路是一一对应的面试讲起来也顺。2.2 三步走找长度、局部翻转、递归衔接递归版的核心思路可以拆成三步第一步从当前节点出发向后走K步。如果走不满K步说明剩下的节点不足一组直接返回当前头节点保持原样。第二步反转从当前节点开始的K个节点。这一步本质就是普通的单链表反转只不过限制反转长度为K。反转之后原来的头节点变成了这一组的尾节点原来的第K个节点变成了这一组的新头。第三步把“这一组的尾节点”的 next 指针指向“剩余链表递归处理后的头节点”。然后返回这一组的新头节点。这里有个非常关键的地方反转前你要先保存“第K1个节点”的位置因为反转过程中会改变指针指向如果不提前保存反转完就找不到后面的链表了。这个细节看似简单却是最容易翻车的点。2.3 边界条件的处理逻辑这道题的边界条件主要有四个我以前每个都踩过链表为空或者K小于等于1直接返回原链表。K等于1意味着每1个一组翻转翻转等于没翻属于无效操作。剩下的节点不足K个保持原顺序直接返回。判断方法就是走K步时提前遇到了NULL。链表长度刚好是K的倍数最后一组也要正常翻转不能多翻也不能少翻。这种情况其实在“走K步刚好走到NULL”时已经处理好了。只有一个节点的情况不管K是多少返回它自己。边界问题最好的处理方式不是靠记忆去背而是在写代码前先画几个测试用例空链表、单节点、长度刚好等于K、长度是K的倍数加1、长度是K的倍数减1。把这几个用例在纸上走一遍边界条件基本就覆盖全了。2.4 用头插法理解“为什么局部反转不会乱”很多人觉得局部反转容易乱其实是没理解头插法的本质。你可以把翻转K个节点想象成做这样一个动作把一串珠子里的前K颗倒个个儿然后再和后面的珠子接上。头插法的过程是依次把当前节点摘下来插到这一组的最前面。第一个节点被插到最前面后变成最后一个第二个节点插到它前面第三个节点又插到更前面如此往复K轮之后原有的顺序就被完全倒过来了。这个过程不涉及跳来跳去的复杂指针变换只要保证“每次摘下当前节点之前先把它的下一个节点用临时变量存起来”就不会断链。很多教科书把这个临时变量叫next我习惯叫tmp意思都一样它是你操作链表的保险绳。3. C语言递归版完整实现逐行拆解3.1 结构体定义与辅助函数先复习一下单链表的标准结构体定义struct ListNode { int val; struct ListNode *next; };这个结构体在力扣里已经给你定义好了本地练习时需要自己写。我每次本地调试都会额外写一个辅助函数用来创建链表和打印链表方便肉眼检查结果。// 根据数组创建链表 struct ListNode* createList(int* arr, int n) { if (n 0) return NULL; struct ListNode* head malloc(sizeof(struct ListNode)); head-val arr[0]; head-next NULL; struct ListNode* cur head; for (int i 1; i n; i) { struct ListNode* node malloc(sizeof(struct ListNode)); node-val arr[i]; node-next NULL; cur-next node; cur node; } return head; } // 打印链表 void printList(struct ListNode* head) { struct ListNode* cur head; while (cur) { printf(%d - , cur-val); cur cur-next; } printf(NULL\n); }这两个函数看起来简单但我强烈建议你写。调试链表题不比调试数组题没有可视化输出全靠脑袋模拟指针变化很容易算错。有个打印函数每次跑完一眼就能看到结果对不对。3.2 局部反转函数两种写法反转K个节点我试过两种写法各有各的适用场景。写法一用循环次数控制反转长度。struct ListNode* reverseK(struct ListNode* head, int k) { struct ListNode* prev NULL; struct ListNode* cur head; while (k--) { struct ListNode* tmp cur-next; cur-next prev; prev cur; cur tmp; } return prev; }这种写法用while (k--)控制循环K次循环结束后prev指向反转后的新头cur指向下一组的起点。前提是调用前已经确保从head开始至少有K个节点。写法二用结束位置控制反转长度。struct ListNode* reverseBetween(struct ListNode* head, struct ListNode* end) { struct ListNode* prev NULL; struct ListNode* cur head; while (cur ! end) { struct ListNode* tmp cur-next; cur-next prev; prev cur; cur tmp; } return prev; }这种写法反转[head, end)这个左闭右开区间也就是从head开始一直反转到end之前的那个节点。它更适合迭代版实现因为迭代版中已经明确知道下一组的起点。我个人在递归版里习惯用写法一因为已经知道了K值直接反转K个最直观。迭代版里则用写法二避免反复数K个节点。3.3 reverseKGroup函数逐行拆解递归版的reverseKGroup函数是整个解法的核心我先把完整代码放出来然后逐行拆解struct ListNode* reverseKGroup(struct ListNode* head, int k) { // 边界条件空链表或 K 小于等于 1直接返回 if (head NULL || k 1) { return head; } // 第一步从 head 出发走 k 步找到第 k 个节点 struct ListNode* cur head; int count 0; while (cur ! NULL count k) { cur cur-next; count; } // 如果走不满 k 步说明剩余节点不足一组保持原样 if (count k) { return head; } // 第二步反转前 k 个节点 // 注意此时 cur 已经指向第 k1 个节点 struct ListNode* newHead reverseK(head, k); // 第三步递归处理剩余链表并把当前组的尾节点接上去 // 原来的 head 反转后变成了这一组的尾节点 head-next reverseKGroup(cur, k); return newHead; }第一段边界条件不多说。第二段走K步是关键循环结束后如果count k说明走到了NULL还没凑够K个直接返回当前头。如果count k那么cur正好指向第K1个节点也就是下一组的起点。注意这里cur的位置非常重要它被用于递归调用所以必须在反转之前就确定并保存好。第三段调用reverseK(head, k)返回反转后的新头newHead。此时原来的head节点已经变成了这一组的尾节点。然后执行head-next reverseKGroup(cur, k)把这一组的尾节点接到“剩余链表递归处理后的头节点”上。最后返回newHead这个返回值就是整个链表反转后的头节点。这里要特别强调一下返回值语义reverseKGroup返回的永远是“传入链表的头节点”但这个头节点在每一层递归里可能已经变了。第一层传入的是原始head返回的是整条链表反转后的头节点第二层传入的是第二组的头节点返回的是第二组反转后的头节点。你只要记住这个函数接受一条链表返回这条链表按K个一组翻转后的头节点。3.4 复杂度分析与算法验证时间复杂度是O(n)其中n是链表节点总数。每个节点最多被访问两次一次在走K步判断长度时一次在反转时。虽然看起来有两轮遍历但两个循环加起来还是线性级别。空间复杂度是O(n/k)这是递归栈的深度。因为每处理完一组K个节点就递归调用一次调用次数等于组数n/k。如果K比较大栈深度会小一些如果K比较小比如K等于2栈深度就是n/2。我在本地用一个长度为7、K等于3的链表做了测试过程如下输入1 - 2 - 3 - 4 - 5 - 6 - 7 第一层反转 1 - 2 - 3得到 3 - 2 - 1cur 指向 4 然后对 4 - 5 - 6 - 7 递归 第二层反转 4 - 5 - 6得到 6 - 5 - 4cur 指向 7 然后对 7 递归 第三层count 1 3不足一组直接返回 7 拼接6 - 5 - 4 的尾节点 4 接到 7 拼接3 - 2 - 1 的尾节点 1 接到 6 - 5 - 4 - 7 输出3 - 2 - 1 - 6 - 5 - 4 - 7跑出来的结果和预期完全一致。这个例子覆盖了两种情况整组翻转和末尾不足一组保持原样回头你验证代码时可以直接用。4. 迭代版改良用哨兵节点消灭递归栈空间4.1 面试官为什么爱追问迭代写法递归版虽然思路清晰但有一个天然缺陷空间复杂度是O(n/k)。如果链表很长、K又很小递归栈会占用不少内存。更麻烦的是如果K刚好等于1递归深度就是n链表一长就容易爆栈。所以面试官经常会追问一句能不能用迭代实现他不是真的觉得递归代码有问题而是想考察你对“递归本质是栈”这件事有没有认知以及能不能用循环手动模拟这个过程。我个人的经验是面试时先把递归版讲清楚然后主动提一句“这个解法空间复杂度是O(n/k)如果需要优化成O(1)空间可以用迭代加哨兵节点实现”面试官通常会对这个加分项很满意。4.2 哨兵节点的妙用迭代版的思路和递归版类似但多了一个非常重要的角色哨兵节点。为什么要用哨兵节点因为每翻转一组头节点都在变化。第一组翻转后原来的头变成了尾新头变成了原来的第K个节点。如果没有哨兵节点每次都要单独判断“当前是不是第一组”代码会多出很多分支。加一个虚拟头节点dummy让dummy-next始终指向当前最新的头节点问题就统一了。迭代版还需要维护几个关键指针prevGroupEnd上一组的尾节点也是当前组拼接的位置。groupStart当前组的第一个节点也就是待反转的起点。nextGroupStart当前组的第K1个节点也就是下一组的起点。整个流程是一个外层循环每次检查剩余节点是否够K个够就反转当前组把上一组接到新头上把当前组的尾节点接到下一组然后更新指针进入下一轮。4.3 迭代版完整代码struct ListNode* reverseKGroup(struct ListNode* head, int k) { if (head NULL || k 1) { return head; } struct ListNode dummy; // 哨兵节点不在堆上分配 dummy.next head; struct ListNode* prevGroupEnd dummy; while (1) { // 检查剩余节点是否够 k 个 struct ListNode* kth prevGroupEnd; for (int i 0; i k; i) { kth kth-next; if (kth NULL) { return dummy.next; // 不足 k 个直接返回 } } // 确定当前组的范围 struct ListNode* groupStart prevGroupEnd-next; struct ListNode* nextGroupStart kth-next; // 反转当前组的 k 个节点 struct ListNode* prev NULL; struct ListNode* cur groupStart; while (cur ! nextGroupStart) { struct ListNode* tmp cur-next; cur-next prev; prev cur; cur tmp; } // 拼接上一组尾节点接到新头当前组尾节点接到下一组 prevGroupEnd-next prev; groupStart-next nextGroupStart; // 更新上一组尾节点为当前组的尾节点 prevGroupEnd groupStart; } }这段代码有几处容易出错的地方需要提醒。第一个是找第K个节点的循环。这里kth初始指向prevGroupEnd然后循环K次每次往后走一步。注意第一次循环时kth-next就是groupStart所以循环结束后kth正好是当前组的第K个节点而不是第K1个。如果中途遇到NULL说明不够K个直接返回dummy.next。第二个是反转区间的控制。while (cur ! nextGroupStart)表示当前组的范围是[groupStart, nextGroupStart)左闭右开。反转结束后prev指向这一组的新头groupStart变成尾节点cur等于nextGroupStart。第三个是拼接顺序。prevGroupEnd-next prev先把上一组的尾接到新头上groupStart-next nextGroupStart再把当前组的尾接到下一组起点。这两个赋值顺序不能反因为groupStart和nextGroupStart都用到了如果先改了groupStart-next后面再用groupStart还是一样的所以谁先谁后其实不影响。真正重要的是拼接必须发生在反转之后而不是之前。第四是更新prevGroupEnd groupStart。注意这里用的是groupStart而不是prev因为groupStart反转后就是当前组的尾节点它是下一轮循环的拼接起点。很多人这里写错成prev导致链表断裂。空间复杂度是O(1)只用了几个临时指针。时间复杂度依然是O(n)每个节点同样最多访问两次。4.4 递归版和迭代版怎么选我把两个版本放在一起对比过列一个表格方便你选择对比项递归版迭代版思路清晰度高和题目描述直接对应中需要理解多个指针维护代码量较简洁稍长空间复杂度O(n/k)O(1)边界处理难度较容易较容易但有更多指针要维护面试沟通效率高容易讲明白中需要画图辅助说明我的建议是笔试和刷题用递归版省时间、留着精力想其他题面试如果被问到优化再默写迭代版。两个都写熟才是这道题的正确打开方式。5. 常见错误与调试实录5.1 错误一没有保存next指针导致断链这是我见过最多的错误也是新手最容易犯的。反转链表时每走一步都要先把cur-next保存到临时变量里因为一旦执行cur-next prev原来的下一个节点就找不回来了。如果你在反转过程中发现最后输出只有第一个节点或者链表凭空少了一截十有八九是这里出了问题。正确做法是在cur-next prev之前先写struct ListNode* tmp cur-next;然后用tmp往后推进。这句话值得写成注释贴在代码最上面链表的任何指针修改先保存后继。5.2 错误二反转次数多算一次或少算一次还拿反转K个节点举例。如果你用while (k--)循环体执行K次后cur指向第K1个节点。但如果你不小心写成了while (--k)或者while (k 1)循环只执行K-1次反转结果就会少一个节点。我调试时碰到过一种很隐蔽的情况K等于3我写while (--k)结果反转完只剩两个节点被翻转第三个节点还挂在后面。从输出看只是顺序不对代码检查时却不容易发现。排查方法很简单在循环里打一个计数器看看到底执行了几次。5.3 错误三不足K个也反转了递归版里如果走K步时遇到NULL应该直接返回当前头。但很多人写完while (cur count k)之后忘了检查count k的情况直接就去反转了。结果就是最后一组不足K个的节点也被翻转和题目要求不符。一个实用的自查技巧测试用例里一定要包含“链表长度不是K的整数倍”的case。比如长度为5、K为2或者长度为7、K为3跑一遍就能暴露这个问题。5.4 错误四递归返回的节点接错递归版里有一行head-next reverseKGroup(cur, k)。这里的head是什么它是一组反转前的头节点反转后变成这一组的尾节点。所以要把它的 next 指向剩余链表处理后的头。如果这里你写成了newHead-next或者写成cur-next结果都会错。newHead是整组的新头它的 next 应该指向这一组内的下一个节点而不是剩余链表。很多人在这一步绕进去其实是没想清楚反转后这一组内部的连接已经由reverseK完成了head只需要负责组间连接。我建议在写递归时养成一个习惯在注释里写清楚当前节点的角色变化。比如head // 反转前是组内第一个节点反转后是组内最后一个节点这样就不会搞混。5.5 调试技巧写一个打印函数比你干瞪眼强链表题的调试远比数组题麻烦因为你看不到内存里的指针指向。我强烈建议在本地环境里写一个printList辅助函数每做一步关键操作就打印一次链表状态。当年我调这道题时就是靠打印函数一步步看懂了指针变化才彻底理解了递归的执行过程。力扣在线编辑器也支持打印printf也会输出到控制台只是平时不常看到。你完全可以在调试时临时加几行printf确认无误后再删掉。另外一个小技巧用数组辅助构造测试链表。直接手写head-next-next太累了用createList函数从数组初始化可以快速生成任意结构的链表测试用例看得清清楚楚。6. 从这道题延伸出去的考点与刷题建议6.1 和它强相关的变体题这道题刷完有几道题建议顺手一起巩固。总结就是K个一组翻转链表是链表反转系列的集大成者学会它等于同时掌握了反转链表I、II和两两交换节点的核心思路。反转链表力扣206基础版学会三指针迭代和递归两种反转写法。反转链表II力扣92指定区间反转需要定位区间头尾是K个一组翻转的区间版。两两交换链表中的节点力扣24本质上就是K等于2的“K个一组翻转链表”做完这题再去做24会发现极其简单。我刷题时习惯把同类型题放在一起集中做比如一周内专门刷链表反转类。这样知识点会形成网络而不是零散的知识点。单独刷一道题过两周就忘了连着刷一类题才会真正形成肌肉记忆。6.2 面试现场怎么讲这道题如果你在面试中遇到这道题不要上来就写代码先给面试官画图。画链表是数据结构题的基本素养尤其是涉及指针变换的题画图能帮你理清思路也能让面试官看到你的结构化思考。讲题思路可以按这个顺序来先讲递归版从当前头出发走K步不足K个直接返回否则反转前K个递归处理剩余链表然后把两部分接起来。再主动补充迭代版提到递归的空间复杂度是O(n/k)如果希望O(1)空间可以用哨兵节点加循环实现。最后讲边界条件空链表、K等于1、长度不足K、长度刚好是K的倍数。面试官通常会顺着你的思路追问一两个细节比如“迭代版中prevGroupEnd为什么用原来的groupStart更新”“dummy节点行不行用栈上分配还是堆上分配”。这两个问题我建议自己先想明白回答起来会更从容。6.3 刷题方式上的一点个人建议Hot 100不是刷一遍就完事的。我的个人经验是三轮刷法第一轮按标签刷快速过思路第二轮随机打乱检验记忆第三轮只刷错题和不会的题。这道K个一组翻转链表我第一轮刷的时候磕磕绊绊第二轮已经能顺畅写递归版第三轮基本可以默写出两个版本。错题本也很重要。我会给每一道错题记录三行题型分类、卡住的原因、下次要特别注意的点。对于这道题我记的是“指针操作题注意保存next、注意返回值语义”。过了一个月回来看一眼就能回忆起关键坑点。刷题这件事最难的不是代码而是和遗忘作斗争。你不需要一天刷很多题但你需要定期复习尤其是那些让你纠结良久的题。它们才是真正提升你算法水平的部分。每当你觉得自己“又忘了怎么写”说明这个知识点正在真正被你吸收。这道题我到现在都还会偶尔翻出来重新写一遍每次写都有一些新感悟。链表操作的乐趣就在这里指针还是那两根指针但在不同的排列组合下能变出无数种题目。希望你看完这篇能把这道Hot 100里的硬骨头啃下来以后遇到任何链表反转题都能胸有成竹。