LeetCode 25. Reverse Nodes in k-Group: Group-Wise Linked List Reversal

LeetCode 25. Reverse Nodes in k-Group: Group-Wise Linked List Reversal【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文基于本仓库英文题解 problems/25.reverse-nodes-in-k-groups-en.md及中文对照版 problems/25.reverse-nodes-in-k-groups.md展开。25 题是 LeetCode 链表考点中“指针修改 链表拼接”的集大成者它把单链表反转206、区间反转92与分组逻辑组合在一起是面试中区分“会写链表”与“真正理解链表”的经典 hard 题。读完本文你将掌握如何用常数空间把链表按 k 个节点一组原地翻转、如何用 dummy 节点规避头节点被修改的边界问题、以及一个“从右往左按 k 组翻转”的字节跳动面试变形题。1. 题目概述与约束LeetCode 25 题原文描述如下Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.翻译成操作语义给定链表1-2-3-4-5当k 2时返回2-1-4-3-5当k 3时返回3-2-1-4-5。末尾不足 k 个节点的部分保持原顺序这正是“余数节点不翻转”的处理要点。只能使用常数额外空间不能拷贝到数组再操作不能使用 O(n) 辅助栈。不能只改节点的值必须真实地交换节点即通过修改指针完成翻转而不是values swap。最后两条约束直接决定了算法形态必须原地、迭代地操作指针这也意味着本题是“指针操作”类题目的标准训练场。本仓库将本题收录在 collections/hard.md 的困难题合集中理由是它“既考验思路是否清晰又考验指针代码是否写得出、写不错”。2. 核心思路先分组再逐组翻转整体策略非常简单一句话概括从左往右遍历链表按 k 个节点切成一截一截对每一截单独做区间反转。拆成三个子问题如何把链表按 k 个节点分组用计数器count定位每组的边界给定区间(start, end]如何反转这一段区间反转反转完一组后如何把前后两段重新接起来指针重连其中第 2 个子问题“给定首尾节点反转一段链表”正是 problems/206.reverse-linked-list.md整链反转与 problems/92.reverse-linked-list-ii.md区间反转 II所训练的能力。本题相当于把 206 的“整链反转”封装成一个工具函数然后按 k 为单位反复调用。2.1 基础构件单链表的反转206先回顾最基础的操作反转整条链表1-2-3-4-null→4-3-2-1-null。过程如下这也是 problems/206.reverse-linked-list.md 的核心初始化一个prev节点为null每移动一步先用临时节点temp保存当前节点的下一个节点遍历过程中让当前节点指向前一个节点再让prev指向当前节点把当前节点更新为temp。核心四行伪代码ListNode temp curr.next; curr.next prev; prev curr; curr temp;这四行顺序不能乱第 1 行先“留下联系方式”保存后继第 2 行才“修改指针”。如果先执行curr.next prev链表当场断开后面的节点就找不到了——这正是 thinkings/linked-list.md 中总结的“先穿、再排、后判空”技巧的由来。2.2 分组与区间反转25 题的完整流程有了单段反转的能力本题只需要解决两件事怎么确定每一段的边界、反转后怎么接回去。原题解的流程如下以k 3为例用一个count变量在遍历链表时记录当前节点的序号用一个start变量记录当前分组起始位置的前一个节点即上一组的尾也是待接回位置用一个end变量记录当前分组要翻转的最后一个节点当count % k 0时说明凑满一组执行区间反转(start, end]——注意是左开右闭start与end各自是区间边界之外/之内的节点反转完成后start更新为该组反转后的最后一个节点也就是下一组的前驱继续向后若count % k ! 0说明还没凑满一组end后移一步同时count加一。区间反转reverse(start, end)的语义来自题解代码注释非常直观0-1-2-3-4-5-6-7-8 | | start end调用start reverse(start, end)后0-3-2-1-4-5-6-7-8 | | start end即把(start, end)之间的节点就地反转为3-2-1start移动到这一小段的新尾值 1 的节点从而为下一轮分组做好准备。![区间 (start, end] 反转示意](assets/problems/25.reverse-nodes-in-k-groups-3.png)再看一个完整例子head [1,2,3,4,5,6,7,8], k 3。第一组[1,2,3]反转为[3,2,1]第二组[4,5,6]反转为[6,5,4]最后[7,8]不足 3 个节点保持原样最终结果为3-2-1-6-5-4-7-8。2.3 为什么要引入 dummy 节点链表题中有一个高频边界陷阱head 节点可能在操作中被修改。本题中第一组一旦反转原来的head值为 1就不再是链表头了因此不能直接返回head。解法是引入一个虚拟节点dummy ListNode(0) dummy.next head后续所有指针操作都从dummy出发无论链表头怎么变化dummy.next始终指向最终结果的头节点最后统一返回dummy.next即可。在本题示例中head从1变为3而dummy保持不变。这一点在 thinkings/linked-list.md 中被归纳为链表“四个技巧”中的虚拟头把头节点变成中间节点头尾边界就不需要单独特判了本题正是该技巧的典型应用。3. 复杂度分析时间复杂度O(n)其中n是链表长度。每个节点恰好被访问一次整体只做一趟线性扫描 若干次常数时间内的指针重连。空间复杂度O(1)。只使用了dummy / start / end / count以及反转函数内部若干指针变量不随输入规模增长。这也是题目“只允许常数额外空间”约束下的最优解形态。4. 关键点小结题解核心创建一个 dummy 节点dummy ListNode(0)dummy.next head以k为单位对链表分组记录每一组的start和end节点对每一组执行区间反转reverse(start, end.next)并同步更新start、end引用最后返回dummy.next。5. 代码实现5.1 Java原英文题解给出的是迭代解法其中reverse函数接收“区间左边界start不参与反转”和“区间右边界end不参与反转”两个哨兵节点返回反转后子链表的新“尾前驱”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 * * return the reversed lists start node, which is the precedence of node end */ 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; } }要点解读主循环中end是扫描指针count记录已经扫描的节点数一旦count % k 0说明start.next ... end正好是一组 k 个节点调用reverse(start, end.next)注意传入的是end.next这样循环终止条件curr ! end才会停在该组末尾reverse内部curr从start.next出发prev初始为start循环把每个curr.next指向前驱直到curr走到end组外哨兵为止反转完成后start.next prevprev 是该组的旧尾、新头first.next currfirst 是该组的旧头、新尾接回剩余链表返回first新尾供外层更新start。5.2 Python 3原英文题解的 Python 版本与 Java 逻辑完全同构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 start dummy end head count 0 while end: count 1 if count % k 0: start self.reverse(start, end.next) end start.next else: end end.next return dummy.next def reverse(self, start, end): prev, curr start, start.next first curr while curr ! end: temp curr.next curr.next prev prev curr curr temp start.next prev first.next curr return first中文版题解额外提供了一个变体reverse(head, tail, terminal)形式——先向后走 k 步探测“剩余长度是否够一组”不够则直接返回ans.next够则调用reverse(head, tail, tail.next)反转子链表并返回新的头尾再把子链表重新接回原链表。两种写法思想一致后者把“长度预检”显式化了。5.3 JavaScript中文版题解同样提供了 JS 实现风格与 Java/Python 一致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; // 翻转stat - 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; } };三个语言版本的核心模式完全一致dummy start end count足以说明这是一个与语言无关的经典指针操作套路。6. 扩展从右往左按 k 组翻转字节跳动面试题原题解的“扩展”小节收录了一道非常经典的面试变形题要求从右往左以 k 个节点为一组进行翻转ByteDance Interview。以1-2-3-4-5-6-7-8, k 3为例从右往左分组6-7-8反转为8-7-63-4-5反转为5-4-31-2只有 2 个节点少于k 3不翻转。最终返回1-2-5-4-3-8-7-6。思路与从左往右版本思路类似只需做一次预处理——因为“从右往左分组”等价于“先整体反转链表再从左往右按 k 分组反转最后再整体反转一次”反转整个链表对反转后的链表从左往右按 k 个节点一组翻转反转第 2 步得到的链表。用同一个例子验证先反转整条链表8-7-6-5-4-3-2-1从左往右按 k3 分组反转6-7-8-3-4-5-2-1再反转第 2 步的结果1-2-5-4-3-8-7-6。这正好与从右往左分组的期望输出一致。整个流程仍然只依赖 206整链反转与 25分组反转两个能力时间复杂度O(n)、空间复杂度O(1)不变。7. 相关题目与本仓库的延伸阅读problems/206.reverse-linked-list.md反转链表本题的基础构件迭代 递归两种写法注意递归在长链表下可能爆栈problems/92.reverse-linked-list-ii.md反转链表 II区间反转中文版题解提出了p1, p2, p3, p4四点法并指出 25 题可以沿用该视角代码里start/end/first/prev的角色与之对应problems/24.swapNodesInPairs.md两两交换链表中的节点即本题k 2的特殊情形thinkings/linked-list.md链表专题方法论总结了“一个原则、两个考点、三个注意、四个技巧”本题被用作“虚拟头”与“穿针引线”两个技巧的典型例题全仓库题目索引见 SUMMARY.md困难题分类见 collections/hard.md。8. 总结LeetCode 25 题表面上是一道 hard 题但拆解后只有三个动作分组、区间反转、指针重连。它的价值在于把链表题的三大基本功整链反转、区间反转、虚拟头处理边界一次性全部串起来反转子链表时牢记“先保存后继再修改指针”的顺序避免断链与成环头节点可能变化时一律用 dummy 节点兜底最后返回dummy.next分组逻辑用count % k判定边界start与end的更新顺序决定了代码是否正确面试中如果遇到“从右往左 k 组翻转”这类变形先想“能否通过两次整体反转转化回标准形态”。掌握这道题链表类的指针操作基本就过关了。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考