京公网安备11010502063487号给一个链表,每 K 个节点为一组整体翻转,最后剩下不足 K 个的原样保留。比如 a→b→c→d→e→f→g→h,k=3,结果是 c→b→a→f→e→d→g→h——前两组各 3 个都翻转了,最后 g,h 只剩 2 个不够一组,原样留着。
思路是每组先看够不够 k 个,够的话就把这一组头尾颠倒,再把结果接上"剩下部分递归处理"的结果:
def reverse_k_group(head, k):
node = head
count = 0
while node and count < k:
node = node.next
count += 1
if count < k:
return head # 不够k个，原样返回
prev = None
curr = head
for _ in range(k):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
head.next = reverse_k_group(curr, k) # head已经变成这一组的尾节点
return prev # prev是这一组反转后的头节点
values = ['a','b','c','d','e','f','g','h']
reverse_k_group(build_list(values), k=3)
结果: ['c', 'b', 'a', 'f', 'e', 'd', 'g', 'h']
和例子完全一致: True
暴力法思路很直接:转成数组,按 k 个一组手动切片、反转,最后不足 k 个的原样拼回去。覆盖几种容易出错的边界:
测试用例(输入, k): [1..8], k=3 -> 8个节点,k=3,余2个 [1..9], k=3 -> 9个节点,刚好整除 [1..5], k=1 -> k=1,应该完全不变 [1..5], k=5 -> k=5,等于链表长度,整体反转 [1..5], k=6 -> k=6,超过链表长度,原样不变 [1..6], k=2 -> k=2,两两反转 [], k=3 -> 空链表 [1], k=1 -> 单节点全部 8 组用例,算法结果与暴力法逐一比对: 全部一致 = True
这几个边界情况专门挑了容易出错的场景:k 恰好等于链表长度(整体反转)、k 超过链表长度(整个不反转)、k=1(相当于什么都不做)——全部跟暴力法对上号,没有遗漏。
递归版逻辑简洁,但拿一个真实的大链表试一下就露馅了——每处理一组就要递归一层,20 万个节点、k=7,意味着要递归接近 3 万层:
N = 200_000 K = 7 print(sys.getrecursionlimit()) # Python 默认递归深度上限 reverse_k_group(build_list(range(N)), K)当前 Python 递归深度限制: 1000 真实报错: RecursionError: maximum recursion depth exceeded
Python 默认最多递归 1000 层,20 万节点、每 7 个一组要递归近 3 万层,远远超过这个限制,直接真实报错。这不是"理论上可能出问题",是真的跑一下就崩——递归版只适合处理不会太长的链表,生产代码不能这么写。
把递归换成一个 group_prev 指针,循环处理每一组,不再依赖调用栈:
def reverse_k_group_iter(head, k):
dummy = ListNode(0, head)
group_prev = dummy
while True:
node = group_prev
count = 0
while node.next and count < k:
node = node.next
count += 1
if count < k:
break
group_next = node.next
prev = group_next
curr = group_prev.next
while curr != group_next:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
tmp = group_prev.next
group_prev.next = prev
group_prev = tmp
return dummy.next
reverse_k_group_iter(build_list(range(200_000)), k=7)
结果与暴力法一致: True
耗时: 15.9 ms
同样 20 万节点、k=7,迭代版 15.9 毫秒跑完,不再受调用栈深度限制。另外在能安全跑递归版的小规模数据上(500 个节点,k 从 1 到 501 都测了一遍,包括 k 恰好等于长度和超过长度的边界),两版结果逐一交叉验证,全部一致——说明迭代版不是另一套逻辑,只是把递归换成了循环,正确性完全等价。
原始链表:a→b→c→d→e→f→g→h,k=3。点击"下一步"看按组处理的过程。