LeetCode 25. K 个一组翻转链表
题目描述
题意分析
从链表头开始，每连续
k个节点划为一组，分别反转各组内部的连接方向，组与组的先后顺序保持不变。最后如果剩余节点不足k个，这一段必须保持原来的顺序，不能反转。题目要求改变节点连接，不能只交换节点中的值。与反转整条链表相比，这里还要解决三个问题：当前组是否完整、反转到哪里停止、反转后的这一组怎样接回前后两段。
反转后，原组尾成为新组头，原组头成为新组尾。因此每轮先确认有
k个节点，再保存后一段的入口，最后接好这一组的两端。用一个虚拟头节点统一处理第一组，就能在 $O(1)$ 额外空间内完成整个过程。
解法：分组迭代反转
核心思路
[!blue]
用
groupPrev指向当前待处理组的前一个节点。每轮开始时，groupPrev及其之前的链表都已处理完毕，groupPrev.next是还未处理部分的起点。最初让groupPrev指向虚拟头节点dummy，第一组也就拥有了可修改的前驱连接。先从
groupPrev向后走k步，找到本组最后一个节点kth。如果途中走到空节点，说明剩余节点不足k个；由于还没有修改这一段的任何连接，可以直接结束，保留原顺序。只有找到完整组，才保存groupNext = kth.next，将它作为固定的结束边界和后一段入口。反转范围从
groupPrev.next开始，到groupNext之前结束。与普通链表反转一样，用curr指向尚未处理的节点，prev指向已经反转部分的头；区别是这里把prev初始化为groupNext。这样第一步修改原组头的next时，就已经把这个未来的新组尾接到了后一段，反转完后不必再补接尾部。每次先保存
curr.next，再令curr.next = prev，最后移动prev和curr。当curr == groupNext，说明恰好处理完本组的全部节点，此时prev与kth都指向新组头，原组头已经成为接向groupNext的新组尾。还差前一段到本组的连接：把
groupPrev.next改为kth即可。不过在覆盖这条连接之前，要先用oldHead保存它原来指向的旧组头。再令groupPrev = oldHead，它作为新组尾，恰好就是下一组的前驱。这样处理好的前缀增长一整组，下一轮继续维护相同的关系。
解题步骤
- 创建
dummy并令它指向head，初始化groupPrev = dummy。- 从
groupPrev出发向后走k步寻找kth；如果kth为空，返回dummy.next，保留不足一组的尾部。- 保存
groupNext = kth.next，初始化prev = groupNext、curr = groupPrev.next。- 当
curr != groupNext时，依次保存后继、反转连接、移动指针，完成这一组的反转。- 保存旧组头
oldHead = groupPrev.next，再令groupPrev.next = kth，把前一段接到新组头。- 令
groupPrev = oldHead，继续检查下一组。最终头节点从dummy.next取得。
代码实现
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode dummy = new ListNode(0, head);
ListNode groupPrev = dummy;
while (true) {
ListNode kth = groupPrev;
for (int i = 0; i < k && kth != null; i++) {
kth = kth.next;
}
if (kth == null) {
return dummy.next;
}
ListNode groupNext = kth.next;
ListNode prev = groupNext;
ListNode curr = groupPrev.next;
while (curr != groupNext) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
ListNode oldHead = groupPrev.next;
groupPrev.next = kth;
groupPrev = oldHead;
}
}
}
func reverseKGroup(head *ListNode, k int) *ListNode {
dummy := &ListNode{Next: head}
groupPrev := dummy
for {
kth := groupPrev
for i := 0; i < k && kth != nil; i++ {
kth = kth.Next
}
if kth == nil {
return dummy.Next
}
groupNext := kth.Next
prev, curr := groupNext, groupPrev.Next
for curr != groupNext {
next := curr.Next
curr.Next = prev
prev, curr = curr, next
}
oldHead := groupPrev.Next
groupPrev.Next = kth
groupPrev = oldHead
}
}
复杂度分析
- 时间复杂度：$O(n)$，
n为链表节点数。完整组中的每个节点只会在定位组尾和反转时各处理一次，尾部不足一组的节点只被检查一次；虽然有内外循环，总处理次数仍与节点数成正比。- 空间复杂度：$O(1)$，只使用一个虚拟头节点和固定数量的指针，不使用数组或递归栈。
关键点总结
[!green]
- 检查完整性与反转分开：先确认节点数量再修改，避免反转了不完整的尾段后还要恢复。
- 两端连接各有安排：
prev = groupNext让新组尾接向后一段，groupPrev.next = kth让前一段接向新组头。- 前驱应移动到旧组头：它是反转后的组尾，也是下一组前面的节点，不能把
groupPrev移到新组头。- 边界自然处理：
k = 1时每组只有一个节点，连接保持不变但前驱仍向后移动；最后恰好满一组时groupNext为空，反转后新尾节点也正确指向空。
易错点总结
[!yellow]
- 寻找组尾的步数错误：从组前驱
groupPrev出发，需要走k步才到组尾；走k - 1步会少算一个节点。- 少反转一个节点：循环条件必须是
curr != groupNext，不能写成curr != kth，否则第k个节点会被漏掉。- 结束边界跟着改变：
groupNext必须提前保存。反转过程中kth.next会变化，不能继续用它判断是否到达边界。- 丢失旧组头：代码在反转后保存
oldHead仍然有效，因为此前没有修改前驱的groupPrev.next；但必须在把这条连接改为kth之前保存。- 返回了原头节点：第一组反转后头节点可能变化，应返回
dummy.next，原来的head已经是第一组的尾节点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 24. 两两交换链表中的节点 | 中等 | 把k固定为2后即为两两交换，可先用此最小分组练习接回前后链段。 |
| 92. 反转链表 II | 中等 | 每个完整分组可视为一次局部反转，但本题需要重复处理并保留不足k的尾段。 |
| 143. 重排链表 | 中等 | 拆分链表后反转并重新连接；本题按固定长度分组反转，该题从中点拆分并交替合并首尾。 |
| 234. 回文链表 | 简单 | 拆分链表后反转并重新连接；本题按固定长度分组反转，该题反转后半段后比较对称值。 |
| 206. 反转链表 | 简单 | 拆分链表后反转并重新连接；本题按固定长度分组反转，该题完整反转链表。 |