企业官网建设流程全解析

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 个节点切成一截一截，对每一截单独做区间反转。

拆成三个子问题：

1. 如何把链表按 k 个节点分组？（用计数器count定位每组的边界）
2. 给定区间(start, end]，如何反转这一段？（区间反转）
3. 反转完一组后，如何把前后两段重新接起来？（指针重连）

其中第 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 的核心）：

1. 初始化一个prev节点为null；
2. 每移动一步，先用临时节点temp保存当前节点的下一个节点；
3. 遍历过程中，让当前节点指向前一个节点，再让prev指向当前节点；
4. 把当前节点更新为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为例）：

1. 用一个count变量在遍历链表时记录当前节点的序号；
2. 用一个start变量记录当前分组起始位置的前一个节点（即上一组的尾，也是待接回位置）；
3. 用一个end变量记录当前分组要翻转的最后一个节点；
4. 当count % k == 0时，说明凑满一组，执行区间反转(start, end]——注意是左开右闭，start与end各自是区间边界之外/之内的节点；
5. 反转完成后，start更新为该组反转后的最后一个节点（也就是下一组的前驱），继续向后；
6. 若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->1，start移动到这一小段的新尾（值 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. 关键点小结（题解核心）

1. 创建一个 dummy 节点：dummy = ListNode(0)，dummy.next = head；
2. 以k为单位对链表分组，记录每一组的start和end节点；
3. 对每一组执行区间反转reverse(start, end.next)，并同步更新start、end引用；
4. 最后返回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 list's '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 = prev（prev 是该组的旧尾、新头），first.next = curr（first 是该组的旧头、新尾，接回剩余链表），返回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->6；
• 3->4->5反转为5->4->3；
• 1->2只有 2 个节点，少于k = 3，不翻转。

最终返回：1->2->5->4->3->8->7->6。

思路：与从左往右版本思路类似，只需做一次预处理——因为“从右往左分组”等价于“先整体反转链表，再从左往右按 k 分组反转，最后再整体反转一次”：

1. 反转整个链表；
2. 对反转后的链表，从左往右按 k 个节点一组翻转；
3. 反转第 2 步得到的链表。

用同一个例子验证：

1. 先反转整条链表：8->7->6->5->4->3->2->1；
2. 从左往右按 k=3 分组反转：6->7->8->3->4->5->2->1；
3. 再反转第 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