LeetCode 25K 个一组翻转链表Reverse Nodes in k-Group——分组迭代法详解与多语言实现【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本篇技术指南以当前仓库 leetcode 中 problems/25.reverse-nodes-in-k-groups.md 为核心系统讲解 LeetCode 25「K 个一组翻转链表」的题目约束、分组迭代算法思路、复杂度分析以及 Java / Python3 / JavaScript 三种语言的完整可运行实现并延伸至「从后往前按 k 分组翻转」的字节跳动变体题与四点法参考实现。读完本文你将掌握链表区间翻转的基本功、dummy node 哨兵技巧以及 k 分组迭代翻转这一经典面试考点的完整解法脉络。一、题目概述与约束题目地址中文版https://leetcode-cn.com/problems/reverse-nodes-in-k-group/英文版见仓库 problems/25.reverse-nodes-in-k-groups-en.mdhttps://leetcode.com/problems/reverse-nodes-in-k-group/题目描述给你一个链表每k个节点一组进行翻转请你返回翻转后的链表。k是一个正整数它的值小于或等于链表的长度。如果节点总数不是k的整数倍那么请将最后剩余的节点保持原有顺序。示例给定链表1-2-3-4-5当k 2时应当返回2-1-4-3-5当k 3时应当返回3-2-1-4-5说明题目硬性约束也是本解法的设计前提你的算法只能使用常数的额外空间——因此不能借助数组、栈等线性辅助结构只能在链表指针层面原地完成你不能只是单纯的改变节点内部的值而是需要实际进行节点交换——即必须通过修改next指针完成反转禁止取巧重写val。前置知识链表的基本结构、遍历与指针操作。仓库专题文档 thinkings/linked-list.md 系统梳理了链表在 LeetCode 中的 54 道题目6 道上锁并总结了链表解题的三个注意点头尾边界处理、指针循环引用导致死循环、虚拟头节点简化操作本文解法正是这三个注意点的综合应用。二、核心思路按 k 分组 区间翻转题意本质是以k个 nodes 为一组进行翻转返回翻转后的 linked list。解题策略为从左往右扫描一遍链表扫描过程中以 k 为单位把链表分成若干段对每一段进行翻转。2.1 单链表翻转的基本功给定一个链表区间如何翻转核心是一个四步循环初始化一个为null的previous node (prev)遍历链表的同时把当前node (curr)的下一个next指向前一个node (prev)在改变当前 node 的指向之前必须用一个临时变量记录当前 node 的下一个 nodecurr.next否则指针就断了ListNode temp curr.next; curr.next prev; prev curr; curr temp;以翻转整个链表为例1-2-3-4-null经过该循环变为4-3-2-1-null。原文档中配有翻转示意图reverse linked list 为手绘推演仓库 assets/problems 目录还收录了翻转过程的逐步图解其本质就是反复执行「记录后继 → 反转指向 → 前驱后移 → 当前后移」四步。2.2 分组迭代的整体框架本解法对每一组k个 nodes进行翻转维护三个关键游标用一个count变量记录当前遍历到的节点个数用一个start变量记录当前分组的起始节点位置的前一个节点用一个end变量记录要翻转的最后一个节点位置。随后循环推进翻转一组k个 nodes即翻转区间(start, end)——注意start与end都是开区间边界start and end exclusively真正被翻转的是start.next到end之间的 k 个节点翻转完成后start指向翻转后链表的区间尾部节点作为下一组的区间左边界返回该start节点如果count % k ! 0本组节点数不足 k则end向后移动一个end end.next每移动一次count 1直到凑满一组再触发翻转。NOTEdummy node 的必要性一般情况下对链表的操作都有可能会引入一个新的 dummy node因为head有可能会改变。这里 head 从1变为3而dummy (List(0))保持不变最终通过返回dummy.next拿到翻转后的新头。关于虚拟头的原理与三个指针小测验可参考 thinkings/linked-list.md 的「虚拟头」小节——其核心价值在于将头节点变成中间节点简化边界判断同时通过在合适的时候断开连接可以方便地返回链表中间的某个节点25. K 个一组翻转链表 正是这一技巧的典型应用。仓库中对应的手绘推导图可见 assets/problems/25.reverse-nodes-in-k-groups-1.PNG 与 assets/problems/25.reverse-nodes-in-k-groups-2.PNG。2.3 完整推演示例以head[1,2,3,4,5,6,7,8], k 3为例仓库 assets/problems/25.reverse-nodes-in-k-groups-3.png 给出了reverse(start, end)区间翻转函数的前后对比示意图0→1→2→3→4→5翻转(start, end)开区间内节点后变为 0→3→2→1→4→5。整个流程为第一组1-2-3翻转为3-2-1第二组4-5-6翻转为6-5-4第三组7-8不足 3 个节点保持原序。最终结果为3-2-1-6-5-4-7-8。2.4 复杂度分析时间复杂度O(n)其中n是 Linked List 的节点总数每个节点最多被访问常数次空间复杂度O(1)只使用常数个指针变量满足题目「只能使用常数的额外空间」的硬性要求。三、关键点分析创建一个 dummy node虚拟头节点规避头节点被翻转后丢失的问题对链表以 k 为单位进行分组记录每一组的起始和最后节点位置对每一组进行翻转并更新起始与最后的位置引用最后返回dummy.next作为翻转后链表的新头。四、多语言完整实现原文档给出了 Java / Python3 / JavaScript 三份实现它们共享同一套「dummy 分组 区间翻转」框架仅语法不同。以下代码均直接取自仓库文档 problems/25.reverse-nodes-in-k-groups.md可直接复制运行。4.1 Java 实现class ReverseKGroupsLinkedList { public ListNode reverseKGroup(ListNode head, int k) { if (head null || k 1) { return head; } ListNode dummy new ListNode(0); dummy.next head; ListNode start dummy; ListNode end head; int count 0; while (end ! null) { count; // group if (count % k 0) { // reverse linked list (start, end] start reverse(start, end.next); end start.next; } else { end end.next; } } return dummy.next; } /** * reverse linked list from range (start, end), return last node. * for example: * 0-1-2-3-4-5-6-7-8 * | | * start end * * After call start reverse(start, end) * * 0-3-2-1-4-5-6-7-8 * | | * start end * first * */ private ListNode reverse(ListNode start, ListNode end) { ListNode curr start.next; ListNode prev start; ListNode first curr; while (curr ! end){ ListNode temp curr.next; curr.next prev; prev curr; curr temp; } start.next prev; first.next curr; return first; } }代码要点主循环用count % k 0判断是否凑满一组凑满时调用reverse(start, end.next)把end的下一个节点作为区间右开边界传入reverse返回first翻转前区间头即翻转后的区间尾作为下一组的start因此end start.next能正确衔接下一组边界条件head null || k 1提前返回——k 为 1 时无需翻转。4.2 Python3 实现class Solution: # 翻转一个子链表并且返回新的头与尾 def reverse(self, head: ListNode, tail: ListNode, terminal): cur head pre None while cur ! terminal: next cur.next cur.next pre pre cur cur next return tail, head def reverseKGroup(self, head: ListNode, k: int) - ListNode: ans ListNode() ans.next head pre ans while head: tail pre # 查看剩余部分长度是否大于等于 k for i in range(k): tail tail.next if not tail: return ans.next next tail.next head, tail self.reverse(head, tail, tail.next) # 把子链表重新接回原链表 pre.next head tail.next next pre tail head next return ans.next代码要点Python 版采用「先探测后翻转」策略用for i in range(k)预先进位tail若中途tail为空说明剩余节点不足 k直接return ans.next保留原序reverse返回(tail, head)即翻转后的新头、新尾便于把子链表重新接回原链表pre.next head; tail.next next注意 Python 中next作为局部变量名虽可运行实际工程中建议改用nxt以免遮蔽内置函数此处为原文档写法予以保留。4.3 JavaScript 实现/** * param {ListNode} head * param {number} k * return {ListNode} */ var reverseKGroup function (head, k) { // 标兵 let dummy new ListNode(); dummy.next head; let [start, end] [dummy, dummy.next]; let count 0; while (end) { count; if (count % k 0) { start reverseList(start, end.next); end start.next; } else { end end.next; } } return dummy.next; // 翻转start - end的链表 function reverseList(start, end) { let [pre, cur] [start, start.next]; const first cur; while (cur ! end) { let next cur.next; cur.next pre; pre cur; cur next; } start.next pre; first.next cur; return first; } };代码要点结构与 Java 版几乎一一对应count % k 0触发分组翻转reverseList(start, end)使用(start, end)开区间语义闭包内嵌reverseList函数复用外层作用域代码紧凑first记录区间原头翻转后start.next pre接新头、first.next cur接右边界返回first供下一轮使用。五、扩展 1从后往前以 k 个为一组翻转字节跳动面试题原文档给出了一道高频变体要求从后往前以k个为一组进行翻转字节跳动 ByteDance 面试题。例子1-2-3-4-5-6-7-8, k 3从后往前以k 3为一组6-7-8为一组翻转为8-7-63-4-5为一组翻转为5-4-31-2只有 2 个 nodes少于k 3个不翻转注意这与正向版本的规则相反——正向是尾部余数保持原序从后往前则是头部余数保持原序。最后返回1-2-5-4-3-8-7-6这里的思路跟从前往后以k个为一组进行翻转类似可以通过预处理三步走复用既有解法翻转整个链表对翻转后的链表进行从前往后以 k 为一组翻转翻转步骤 2 中得到的链表。以1-2-3-4-5-6-7-8, k 3推演翻转链表得到8-7-6-5-4-3-2-1以 k 为一组翻转6-7-8-3-4-5-2-1翻转步骤 #2 链表1-2-5-4-3-8-7-6三步之后恰好完成「从后往前按 k 分组翻转」且头部不足 k 的余数1-2被保留在原位复杂度仍为O(N)时间、O(1)空间。六、扩展 2与 92 题「四点法」结合的另一份实现原文档指出如果按照 92.reverse-linked-list-ii 中提到的p1, p2, p3, p4四点法思路来思考本题会非常清晰。92 题 的核心在于取出需要反转的那一小段链表反转完后再插入到原先的链表中四个特殊节点分别记录区间前驱p1、区间原头p2、区间新头p3、区间后继p4。将其泛化到「k 个一组」的场景即可得到如下 Python 实现来自原文档class Solution: def reverseKGroup(self, head: ListNode, k: int) - ListNode: if head is None or k 2: return head dummy ListNode(0) dummy.next head pre dummy cur head count 0 while cur: count 1 if count % k 0: pre self.reverse(pre, cur.next) # end 调到下一个位置 cur pre.next else: cur cur.next return dummy.next # (p1, p4 左右都开放 def reverse(self, p1, p4): prev, curr p1, p1.next p2 curr # 反转 while curr ! p4: next curr.next curr.next prev prev curr curr next # 将反转后的链表添加到原链表中 # prev 相当于 p3 p1.next prev p2.next p4 # 返回反转前的头 也就是反转后的尾部 return p2 # lc codeend该实现的要点维护p1区间左边界开区间、p2区间原头、p3翻转后的新头即循环结束时的prev、p4区间右边界开区间reverse方法内完成区间反转后用p1.next prev与p2.next p4将反转段重新拼接回原链表返回p2翻转前的头、翻转后的尾作为下一组的pre从而与主循环的cur pre.next衔接。复杂度分析此实现时间复杂度O(N)空间复杂度O(1)七、相关题目与延伸阅读本题是链表区间翻转家族的核心成员与以下仓库题解互为延伸92.reverse-linked-list-ii反转链表的指定区间m到n「四点法」的出处可视为本题的区间特化版本206.reverse-linked-list反转整个单链表是本题区间翻转的基本功92 题 与 25 题 的公共子问题其文档同时给出了递归实现及「递归会导致线性栈空间、不推荐在生产环境使用」的说明。此外仓库 thinkings/linked-list.md 将本题的两种关键技巧归纳为虚拟头dummy node将头节点变成中间节点简化边界判断本题正是「返回虚拟头的 next」以应对头节点被翻转改动的典型案例见该文档「虚拟头」小节穿针引线拼接链表先反转子链表再将其拼接回原链表本题与 61. 旋转链表、92 题 均采用此方法该方法通常不是最优解但好理解、易书写、不易出错适合新手见该文档「穿针引线」小节。对于链表题 90% 的 bug 都出现在头尾节点处理与指针循环引用这两类问题上见 206 题文档建议在阅读与练习本题时保持对这两个问题的警惕画图推演后再落笔写码。参考资料LeetCode 官方题目英文版https://leetcode.com/problems/reverse-nodes-in-k-group/对应仓库 problems/25.reverse-nodes-in-k-groups-en.mdLeetCode 官方题目中文版https://leetcode-cn.com/problems/reverse-nodes-in-k-group/LeetCode DiscussionNon-recursive Java solution and idea, by yellowstonehttps://leetcode.com/problems/reverse-nodes-in-k-group/discuss/11440/Non-recursive-Java-solution-and-idea原文档 References 部分引用为迭代解法的思路来源之一【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考