大四双非春招学习记录-K 个一组反转链表

手撕 K 个一组反转链表这些细节你必须知道前言大四双非春招学习记录LeetCode 第 25 题「K 个一组翻转链表」是链表类题目中的困难题也是面试中的高频考题。很多同学看到「困难」标签就望而却步但实际上只要掌握了核心思路这道题并没有想象中那么难。本文将带你从零开始逐步攻克这道题并总结出通用的解题模板。一、题目理解1.1 题目描述给你一个链表每 k 个节点一组进行反转返回反转后的链表。如果节点总数不是 k 的整数倍最后剩余的节点保持原有顺序。示例 1输入head [1,2,3,4,5], k 2 输出[2,1,4,3,5]图解1 - 2 - 3 - 4 - 5 ↓ 反转第一组 2 - 1 - 3 - 4 - 5 ↓ 反转第二组 2 - 1 - 4 - 3 - 5示例 2输入head [1,2,3,4,5], k 3 输出[3,2,1,4,5]1.2 关键信息提取✅ 每 k 个节点一组进行反转✅ 不足 k 个的节点保持原样✅ 需要原地修改链表不能只改值✅ 空间复杂度要求 O(1)二、前置知识在攻克这道题之前你需要掌握以下基础2.1 链表的基本操作// 链表节点定义functionListNode(val,next){this.valvalundefined?0:val;this.nextnextundefined?null:next;}// 遍历链表letcurhead;while(cur){console.log(cur.val);curcur.next;}2.2 反转整个链表functionreverseList(head){letprevnull;letcurhead;while(cur){letnextcur.next;// 保存下一个节点cur.nextprev;// 反转指针prevcur;// 移动 prevcurnext;// 移动 cur}returnprev;// 返回新的头节点}图解反转过程初始: null - 1 - 2 - 3 第一步: null - 1 - 2 - 3 第二步: null - 1 - 2 - 3 完成: 3 - 2 - 1 - null2.3 虚拟头节点技巧虚拟头节点dummy node是链表题目中常用的技巧可以统一处理边界情况。// 没有虚拟头节点letnewHeadhead;if(条件){newHeadhead.next;// 需要特殊处理}// 使用虚拟头节点letdummynewListNode(0);dummy.nexthead;letprevdummy;// 统一处理不需要特殊判断三、核心思路3.1 整体流程K 个一组反转链表的核心思路可以概括为 4 步┌─────────────────────────────────────┐ │ 1. 找到当前组的头节点和尾节点 │ │ 2. 保存下一组的起始节点 │ │ 3. 反转当前组 │ │ 4. 连接回原链表 │ └─────────────────────────────────────┘ ↓ 重复以上步骤直到结束3.2 图解整体流程以1-2-3-4-5, k2为例初始状态 dummy → 1 → 2 → 3 → 4 → 5 → null ↑ prev 第1组节点1-2 dummy → 1 → 2 → 3 → 4 → 5 → null ↑ ↑ head tail 反转后 dummy → 2 → 1 → 3 → 4 → 5 → null ↑ ↑ head tail 连接并移动指针 dummy → 2 → 1 → 3 → 4 → 5 → null ↑ ↑ prev head下一组起点 第2组节点3-4 dummy → 2 → 1 → 3 → 4 → 5 → null ↑ ↑ head tail 反转后 dummy → 2 → 1 → 4 → 3 → 5 → null ↑ ↑ head tail 连接并移动指针 dummy → 2 → 1 → 4 → 3 → 5 → null ↑ prev headnull结束四、代码实现4.1 完整代码迭代法varreverseKGroupfunction(head,k){// 边界情况if(!head||k1)returnhead;// 创建虚拟头节点letdummynewListNode(0);dummy.nexthead;letprevdummy;// prev 指向每组的前一个节点letcurhead;// 先计算链表长度letlen0;letphead;while(p){len;pp.next;}// 需要反转的组数letgroupsMath.floor(len/k);// 反转每一组for(leti0;igroups;i){// 反转当前组的 k 个节点for(letj1;jk;j){letnextcur.next;// 要移动的节点cur.nextnext.next;// 跳过 next 节点next.nextprev.next;// next 指向当前组的头prev.nextnext;// prev 指向新的头}// 移动指针到下一组prevcur;curcur.next;}returndummy.next;};4.2 更易理解的版本带辅助函数varreverseKGroupfunction(head,k){// 创建虚拟头节点letdummynewListNode(0);dummy.nexthead;letprevdummy;while(head){// 1. 找到当前组的尾节点lettailprev;for(leti0;ik;i){tailtail.next;if(!tail)returndummy.next;// 不足 k 个直接返回}// 2. 保存下一组的起始节点letnextGrouptail.next;// 3. 反转当前组 [head, tail][head,tail]reverseList(head,tail);// 4. 连接回原链表prev.nexthead;tail.nextnextGroup;// 5. 移动指针到下一组prevtail;headnextGroup;}returndummy.next;};// 反转链表的一部分 [head, tail]functionreverseList(head,tail){letprevtail.next;// 关键prev 指向 tail 的下一个节点letcurhead;while(prev!tail){letnextcur.next;cur.nextprev;prevcur;curnext;}return[tail,head];// 返回新的头尾}4.3 递归解法简洁优雅varreverseKGroupfunction(head,k){// 找到第 k1 个节点lettailhead;for(leti0;ik;i){if(!tail)returnhead;// 不足 k 个不反转tailtail.next;}// 反转前 k 个节点letnewHeadreverseFirstK(head,k);// 递归处理后续节点head.nextreverseKGroup(tail,k);returnnewHead;};// 反转前 k 个节点返回新的头节点functionreverseFirstK(head,k){letprevnull;letcurhead;for(leti0;ik;i){letnextcur.next;cur.nextprev;prevcur;curnext;}returnprev;}五、关键点详解5.1 为什么需要虚拟头节点// 没有虚拟头节点时第一组需要特殊处理letnewHeadhead;if(第一组需要反转){newHead反转后的头;}// 使用虚拟头节点统一处理letdummynewListNode(0);dummy.nexthead;letprevdummy;// prev 始终指向前一个节点5.2 反转函数中的 prev 为什么要指向 tail.nextfunctionreverseList(head,tail){letprevtail.next;// 关键点letcurhead;while(prev!tail){letnextcur.next;cur.nextprev;prevcur;curnext;}return[tail,head];}图解说明反转前head → ... → tail → nextGroup → ... ↓ 反转时prev 应该指向 nextGroup 这样反转后tail 的 next 自然就指向 nextGroup5.3 为什么反转后要返回 [tail, head]// 反转前[head]→...→[tail]→ nextGroup// 反转后[tail]→...→[head]→ nextGroup// ↑新头 ↑新尾// 所以返回 [新头, 新尾] [tail, head]六、常见错误与调试错误 1指针丢失// ❌ 错误写法letnextcur.next;cur.nextprev;prevcur;curcur.next;// 此时 cur.next 已经被修改// ✅ 正确写法letnextcur.next;cur.nextprev;prevcur;curnext;// 使用之前保存的 next错误 2边界判断错误// ❌ 错误提前 break 会导致逻辑混乱for(leti0;ik;i){tailtail.next;if(!tail)break;}// ✅ 正确直接返回for(leti0;ik;i){tailtail.next;if(!tail)returndummy.next;}错误 3连接顺序错误// ❌ 错误prev.nexttail;// tail 是反转前的尾head.nextnextGroup;// ✅ 正确prev.nexthead;// head 现在是反转后的头tail.nextnextGroup;七、测试用例// 辅助函数数组转链表functionarrayToList(arr){letdummynewListNode(0);letcurdummy;for(letvalofarr){cur.nextnewListNode(val);curcur.next;}returndummy.next;}// 辅助函数链表转数组functionlistToArray(head){letresult[];while(head){result.push(head.val);headhead.next;}returnresult;}// 测试用例1正常情况lethead1arrayToList([1,2,3,4,5]);console.log(listToArray(reverseKGroup(head1,2)));// [2,1,4,3,5]// 测试用例2k1lethead2arrayToList([1,2,3,4,5]);console.log(listToArray(reverseKGroup(head2,1)));// [1,2,3,4,5]// 测试用例3k 大于链表长度lethead3arrayToList([1,2,3]);console.log(listToArray(reverseKGroup(head3,5)));// [1,2,3]// 测试用例4正好整数倍lethead4arrayToList([1,2,3,4]);console.log(listToArray(reverseKGroup(head4,2)));// [2,1,4,3]// 测试用例5空链表console.log(listToArray(reverseKGroup(null,2)));// []// 测试用例6单节点lethead6arrayToList([1]);console.log(listToArray(reverseKGroup(head6,2)));// [1]八、复杂度分析解法时间复杂度空间复杂度迭代法O(n)O(1)递归法O(n)O(n/k)递归栈时间复杂度每个节点被访问常数次总体 O(n)空间复杂度迭代法 O(1)递归法 O(n/k)递归深度九、相关题目推荐掌握了这道题下面这些题目会变得简单很多题目难度相似度核心区别206. 反转链表简单⭐⭐⭐整体反转92. 反转链表 II中等⭐⭐⭐⭐反转指定区间24. 两两交换链表中的节点中等⭐⭐⭐⭐⭐k2 的特例61. 旋转链表中等⭐⭐链表旋转十、面试技巧面试官可能会问的问题Q1能否用递归实现时间复杂度是多少可以递归实现更简洁但空间复杂度 O(n/k)递归栈深度。如果 k 很大可能会导致栈溢出。Q2如果 k0 怎么办k 是正整数题目保证 k0。但可以和面试官讨论边界处理。Q3如何测试你的代码可以从以下角度测试空链表单节点链表k1k链表长度链表长度正好是 k 的整数倍链表长度不是 k 的整数倍Q4能优化吗可以先遍历一次计算长度避免在循环中重复检查边界。十一、总结口诀创建虚拟头prev 指向它 循环条件 head 不空 找够 k 个点不够就回家 保存下一组反转当前它 连接前后段指针往后拉 重复以上步直到结束啦写在最后K 个一组反转链表虽然标记为「困难」但它本质上是「反转链表」「分组处理」的组合。只要掌握了基础的反转算法理解了指针的操作这道题就能迎刃而解。记住核心心法先找到一组反转它接回去找下一组建议多画图、多调试把指针的变化过程在脑海中过一遍。当你能够清晰地画出每一步的指针变化代码自然就写出来了。如果这篇文章对你有帮助欢迎点赞收藏也欢迎在评论区交流讨论