25. K 个一组翻转链表 (Hard)
专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/reverse-nodes-in-k-group/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你链表的头节点 head，每 k 个节点一组进行翻转，返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
- 输入：head = [1,2,3,4,5], k = 2
- 输出：[2,1,4,3,5]
- 输入：head = [1,2,3,4,5], k = 3
- 输出：[3,2,1,4,5]
题目详细分析
- 数据范围： 链表中节点数在 [1, 5000] 范围内，节点值在 [0, 1000] 范围内，k ≤ 链表长度
- 输入特征： 单链表，需要按 K 个一组分段翻转
- 核心约束： 不能修改节点值，必须实际交换节点。空间复杂度 O(1)
- 隐藏条件： 难点不在于翻转本身，而在于「组间连接」——翻转后每组的首尾需要与前后组的正确连接
- 边界条件： k = 1（不需要翻转）、k = 链表长度（全部翻转）、剩余不足 k 个节点（保持原样）
小白版直白理解
还是那串珠子，这次要按每 K 颗一组来翻转子串。
比如每 2 颗一组，珠子颜色是 [红,蓝,绿,黄,紫] → 变成 [蓝,红,黄,绿,紫]（最后一颗不够一组不动）。 每 3 颗一组：→ [绿,蓝,红,紫,黄]（最后两颗不够一组不动）。
关键在于：每一组翻转之后的「新头」需要接到上一组的「新尾」，这一组的「新尾」要接到下一组的「新头」。就像把几节反转过的链子再连接起来。
解题思路
思路一：迭代法 + 虚拟头节点（推荐）
为什么这样想： 将问题拆分成三个子问题：
- 检测当前是否还有 K 个节点（不够则直接返回）
- 翻转一个长度为 K 的子链表（复用 206 题的反转逻辑）
- 组间重连（将翻转后的组正确地接入主链）
关键洞察： 翻转 K 个节点前，需要记录四个关键位置：前驱节点 pre、当前组头节点 group_head、当前组尾节点（即原 group_head，翻转后变成尾）、下一组的头节点 next_group。翻转后：pre.next = 新头，group_head.next = next_group。
def reverseKGroup(head, k):
"""迭代法：虚拟头节点 + 分组翻转 + 组间重连"""
if not head or k == 1:
return head
dummy = ListNode(0, head)
pre = dummy # 上一组的末尾（也是当前组的前驱）
while True:
# 1. 检查是否有 K 个节点
cur = pre
for _ in range(k):
cur = cur.next
if not cur:
return dummy.next # 不足 K 个，结束
# 2. 翻转 K 个节点
group_head = pre.next # 当前组的第一个节点（将成为最后一个）
next_group = cur.next # 下一组的头节点
# 翻转 [group_head, cur] 这一段
prev, curr = None, group_head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# 翻转后 prev 是新头，group_head 是尾
# 3. 组间重连
pre.next = prev # 前驱指向新头
group_head.next = next_group # 当前组尾指向下一组
pre = group_head # pre 移到当前组尾（即下一组的前驱）
def reverse(head, k):
"""辅助函数：翻转长度为 K 的子链表，返回新头"""
pre, cur = None, head
for _ in range(k):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre思路二：递归法
思路讲解： 递归地处理每一组。先检查是否有 K 个节点，有则翻转当前组，然后递归处理下一组，并将当前组的尾节点指向递归结果。
def reverseKGroup(head, k):
"""递归法"""
if not head:
return None
# 检查是否有 K 个节点
cur = head
count = 0
while cur and count < k:
cur = cur.next
count += 1
if count < k:
return head # 不足 K 个，原样返回
# 翻转前 K 个节点
prev, curr = None, head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# 递归处理后续链表
head.next = reverseKGroup(curr, k) # head 现在是当前组的尾
return prev # prev 是当前组的新头思路三：使用栈辅助（不推荐，但好理解）
思路讲解： 每次取 K 个节点入栈，然后依次弹出实现翻转。弹出的节点依次接到结果链表后面。最后不足 K 个的节点保持原序接入。
def reverseKGroup(head, k):
"""栈辅助法（空间 O(k)）"""
dummy = ListNode(0)
cur = dummy
while True:
stack = []
temp = head
# 尝试取 K 个节点
for _ in range(k):
if not temp:
# 不足 K 个，保持原序
cur.next = head
return dummy.next
stack.append(temp)
temp = temp.next
# 弹出实现翻转
while stack:
cur.next = stack.pop()
cur = cur.next
head = temp # 指向下一组的头
cur.next = None # 断开，防止成环
return dummy.next易错点
- 不足 K 个的处理： 剩余不足 K 个时保持原序，不能翻转。检查时机是翻转之前
- 组间连接： 翻转后 group_head.next 必须指向 next_group，否则链表会在组间断裂
- pre 的更新： 每次处理完一组后，pre 要更新为 group_head（翻转后的组尾），它是下一组的前驱
- dummy.next 的返回： 必须返回 dummy.next，因为原 head 可能已不在链首
- K=1 的优化： k=1 时不需要任何操作，可以直接返回 head
- 边界： 空链表或 k=1，直接返回 head
框架提炼
K 个一组翻转模板： 将复杂的链表分段操作拆解为标准化的步骤。
# 整体框架
dummy = ListNode(0, head)
pre = dummy
while True:
# 1. 检查是否有 K 个节点
cur = pre
for i in range(k):
cur = cur.next
if not cur: return dummy.next
# 2. 翻转当前组
group_head = pre.next
next_group = cur.next
pre.next = reverse(group_head, k) # 前驱指向新头
group_head.next = next_group # 组尾指向下一组
# 3. 移动 pre
pre = group_head
# 翻转子函数
def reverse(head, k):
pre, cur = None, head
for _ in range(k):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre这个模板的核心思想是「先检测、再处理、后重连」，适用于各类需要分段处理链表的问题。
关联题目
- 206-反转链表 — 本题的翻转子操作，单链表翻转是基础
- 24-两两交换链表中的节点 — K = 2 的特化版本，比本题简单
- 92-反转链表II — 反转链表的指定区间