你好，同学。欢迎来到 NOI 专题训练营的“链表三部曲”终章。

在掌握了“全链表反转”和“区间反转”之后，今天我们要挑战的是链表操作中的“大综合题”——K 个一组翻转链表。这道题在 LeetCode 上被标为困难（Hard），在 NOI 竞赛中，它代表了对复杂逻辑控制和边界处理的最高要求。

一、 题目描述 (NOI 风格)

【题目名称】 K 个一组翻转链表 (Reverse Nodes in k-Group) 【时间限制】 1.0s 【内存限制】 256MB

【问题描述】 给你一个链表的头节点 head，每 k 个节点一组进行翻转，并返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的倍数，那么最后剩余的节点应当保持原有顺序。 注意：

1. 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
2. 你的算法只能使用常数的额外空间。

【输入格式】 第一行包含链表的各节点值，以空格隔开。 第二行包含一个正整数 $k$。

【输出格式】 输出处理后的链表序列。

【样例 1 输入】

1 2 3 4 5
2

【样例 1 输出】

2 1 4 3 5

【样例 2 输入】

1 2 3 4 5
3

【样例 2 输出】

3 2 1 4 5

【数据范围】

• 链表中节点的数目为 $n$。
• $1 \le k \le n \le 5000$。
• $0 \le Node.val \le 1000$。

二、 预备知识点

1. 区间反转的封装：将一段长度为 $k$ 的链表看作一个整体进行反转。
2. 分组迭代逻辑：如何准确判断剩余节点是否足够 $k$ 个。
3. 多指针衔接：在反转完一组后，如何将上一组的“尾”连向这一组的新“头”，并让这一组的“新尾”指向下一组的“旧头”。

三、 启发式教学：草稿纸上的推理过程

这道题的难点在于**“模块化思维”**。不要试图在大循环里处理所有指针，要把问题拆开。

1. 宏观流程 (草稿纸演练)

假设链表：[1 -> 2 -> 3] -> [4 -> 5 -> 6] -> 7, $k=3$。

• 第一步：确认是否有 3 个节点。有（1, 2, 3）。
• 第二步：反转该区间。得到 3 -> 2 -> 1。此时 1 是尾，3 是头。
• 第三步：记住下个区间的起始点（4）。
• 第四步：将 1 的 next 连向后续处理的结果。
• 第五步：移动到 4，重复以上步骤。
• 第六步：剩余节点（7）不足 3 个，保持原样返回。

2. 微观连接 (核心痛点)

反转一组 [start ... end] 后：

• 该组的前驱节点（pre）应该指向 end。
• 该组的 start 应该指向下一组的开头（nextGroupHead）。

关键： 每反转完一组，当前的 start 就会变成下一组的 pre。

四、 算法流程图 (迭代法逻辑)

在 Mermaid 语法中，我们使用圆括号 ( ) 避开特殊符号。

graph TD
    Start("开始") --> Dummy("创建 Dummy 节点指向 head")
    Dummy --> SetPre("令 pre 等于 dummy")
    SetPre --> CheckK{"往后走 k 步能到末尾吗?"}
    
    CheckK -- "不能 (不足k个)" --> Finish("返回 dummy 的 next")
    
    CheckK -- "能 (找到 end 节点)" --> SaveNext("1. 记录下组开头 nextHead 为 end 的 next")
    SaveNext --> Cut("2. 断开当前组: end 的 next 设为 NULL")
    Cut --> CallReverse("3. 反转当前组: reverse(pre 的 next)")
    CallReverse --> ConnectPre("4. 衔接前驱: pre 的 next 设为反转后的新头")
    ConnectPre --> ConnectNext("5. 衔接后继: 原区间头部的 next 设为 nextHead")
    ConnectNext --> UpdatePre("6. 移动 pre 到原区间头部-现区间尾部")
    UpdatePre --> CheckK

五、 复杂度分析与优化建议

• 时间复杂度：$O(n)$。

  • 我们需要遍历链表来计数（$O(n)$）。
  • 翻转操作中，每个节点最多被翻转一次（$O(n)$）。
  • 总时间复杂度为线性。

• 空间复杂度：

  • 迭代法：$O(1)$，只用了有限的辅助指针。符合题目要求。
  • 递归法：$O(n/k)$，递归深度取决于分组数，会占用系统栈空间。在 NOI 严苛的内存限制下，建议优先使用迭代。

优化建议：

1. 跳出检查：在每一组反转前，先探路看后面够不够 $k$ 个。如果不够，直接 break。
2. 指针重置：翻转函数可以返回 newHead 和 newTail，方便主函数衔接。

六、 读题关键词总结

在处理这类“K 个一组”或“每间隔 X”操作的题目时，注意：

1. “不足 $k$ 个保持原序”：这意味着你必须先**“预检”**（Lookahead），而不是边反转边检查。
2. “实际进行节点交换”：明示禁止 node->val = temp 这种取巧操作，必须通过修改 next 指针实现。
3. “常数额外空间”：这是一个强信号，要求你使用**迭代（Loop）**而非递归，或者确保递归深度非常小。
4. “返回反转后的头节点”：提示你链表的入口可能会变，使用 Dummy Node 是标准起手式。

教练寄语： 同学，这道题是链表操作的“大成之作”。如果你能独立在草稿纸上把那 4-5 个关键指针（pre, start, end, nxt）在每一轮循环中的指向变化画清楚，那么整个 NOI 阶段的线性链表逻辑你就彻底通关了！加油。