企业官网建设流程全解析

LeetCode 25. Reverse Nodes in k-Group 题解：Go 递归实现 K 个一组反转链表

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 25. Reverse Nodes in k-Group 题解文档 展开，深入讲解"链表按 K 个节点一组反转、尾部不足 K 个保持原样"这一经典链表操作问题，并结合本仓库中对应的 Go 源码实现 与 单元测试，逐行剖析其递归 + 局部区间反转的实现原理。读完本文，你将掌握递归切割链表的通用框架、"区间反转"辅助函数的写法、复杂度分析方法，以及它与 Problem 24 Swap Nodes in Pairs 的递进关系。

题目重述

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

给定一个单链表，每次以 k 个节点为一组进行反转，并返回修改后的链表。

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.

k 是正整数，且小于等于链表长度。如果链表末尾剩余节点数不足 k 个，则这些节点保持原样，不参与反转。

示例

Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5 For k = 3, you should return: 3->2->1->4->5

• k = 2 时：链表被切成[1,2]、[3,4]、[5]三组，前两组各自反转，末尾孤立的5保持不动；
• k = 3 时：第一组[1,2,3]反转成[3,2,1]，剩余[4,5]不足 3 个节点，原样保留。

关键约束

• Only constant extra memory is allowed.只允许使用常数级别的额外内存；
• You may not alter the values in the list's nodes, only nodes itself may be changed.不允许修改节点内部的数值，只能通过调整节点的Next指针来改变链表结构。

第二条约束意味着不能采用"先取出 k 个值、反转后再写回"的取巧方案，必须老老实实做指针重连。

题目大意

原题解文档用一句话概括了本题的核心要求：

按照每 K 个元素翻转的方式翻转链表。如果不满足 K 个元素的就不翻转。

即：将链表从左到右按固定步长 K 切成若干段，每段内部做完整反转；最后一段若长度不足 K，则整段原封不动。

解题思路：递归 + 区间反转

本题解文档明确指出它与 Problem 24 的递进关系：

这一题是 problem 24 的加强版，problem 24 是两两相邻的元素，翻转链表。而 problem 25 要求的是 k 个相邻的元素，翻转链表，problem 相当于是 k = 2 的特殊情况。

Problem 24 是"两两交换"（k = 2 的特例），而本题把步长从固定的 2 推广到任意正整数 k。本仓库给出的实现采用递归框架，整体思路分三步：

1. 探路（探测 k 步）：从当前段头节点出发前进 k 步。若中途遇到nil，说明剩余节点不足 k 个，直接返回当前头节点（这一段不反转）。
2. 区间反转：对head, node)这个左闭右开区间内的 k 个节点执行反转，返回反转后的新头节点。
3. 递归拼接：将反转后的段尾（即原 head）接到后续段递归处理的结果上，层层组装成完整链表。

这种"先切段、段内反转、递归处理剩余"的模式，是链表题中非常通用的一种递归切割写法。

源码逐行解析

核心实现位于 [25. Reverse Nodes in k Group.go，共两个函数：

package leetcode import ( "github.com/halfrost/LeetCode-Go/structures" ) // ListNode define type ListNode = structures.ListNode func reverseKGroup(head *ListNode, k int) *ListNode { node := head for i := 0; i < k; i++ { if node == nil { return head } node = node.Next } newHead := reverse(head, node) head.Next = reverseKGroup(node, k) return newHead } func reverse(first *ListNode, last *ListNode) *ListNode { prev := last for first != last { tmp := first.Next first.Next = prev prev = first first = tmp } return prev }

reverseKGroup：递归主函数

node := head for i := 0; i < k; i++ { if node == nil { return head } node = node.Next }

这一小段是"探路"逻辑：从head出发走 k 步。若第 k 步之前就遇到nil，说明当前段不足 k 个节点，直接return head——这与题目"末尾不足 k 个不反转"的要求完全对应。走完 k 步后，node恰好指向当前段之后的第一个节点，即下一段的起点（也可能是nil）。

newHead := reverse(head, node)

调用辅助函数reverse，对head, node)区间内的 k 个节点进行反转。注意区间是左闭右开的：head在区间内，node不在区间内。反转完成后返回新头节点newHead，即原区间内的最后一个节点。

head.Next = reverseKGroup(node, k)

这是递归的关键拼接：反转后，原head变成了当前段的尾节点，它的Next应该指向后续段的处理结果。而后续段从node开始，同样以 k 为步长递归处理，于是递归调用reverseKGroup(node, k)并把返回值接到head.Next上。

return newHead

向上一层返回当前段反转后的新头节点，供上一层拼接。

reverse：区间反转辅助函数

prev := last for first != last { tmp := first.Next first.Next = prev prev = first first = tmp } return prev

这是标准的"区间内指针逆置"写法：

• prev初始化为last。由于last不在反转区间内，它恰好作为区间首节点反转后的"后继"，把first.Next指向它就能让反转后的区间尾部自然接上后续链表（后续可能是下一段的头，也可能是nil）；
• 循环条件first != last保证区间开区间语义：last本身不会被反转；
• 每轮迭代中，先用tmp暂存first.Next，再把first.Next指向prev，随后prev、first同步前移，实现就地指针反转；
• 循环结束时first == last，此时prev指向区间内最后一个被处理的节点，即反转后的新头，返回prev即可。

这种"将prev初始化为区间外节点"的技巧，避免了在反转前先断开链表、反转后再手动接尾的繁琐操作，是区间反转的高效写法。

测试用例验证

仓库为本题提供了 [单元测试，覆盖两个典型场景：

第二个用例很有价值：当k = 1时，探路循环走一步即到达nil，直接返回head，因此链表原样输出——这验证了递归框架在退化场景下依然正确。

测试驱动方式同样值得学习：

fmt.Printf("【input】:%v 【output】:%v\n", p, structures.List2Ints(reverseKGroup(structures.Ints2List(p.one), p.two)))

它借助 structures 包 提供的两个转换函数完成"切片 ⇄ 链表"互转：

• Ints2List(nums []int) *ListNode：把整数切片构建成链表，便于构造测试输入；
• List2Ints(head *ListNode) []int：把链表还原成整数切片，便于断言输出。

其中List2Ints内置了深度上限 100 的环检测（超过即 panic），见 structures/ListNode.go，可有效防止因误构造环形链表导致死循环。链表节点本身定义在 structures/ListNode.go：

type ListNode struct { Val int Next *ListNode }

题解文件顶部通过type ListNode = structures.ListNode建立类型别名，使解法代码可以直接复用统一的链表结构，无需重复定义。

运行测试的方式（仓库根目录下）：

go test ./leetcode/0025.Reverse-Nodes-in-k-Group/ -v

复杂度分析

• 时间复杂度：O(n)。探路阶段每个节点至多被访问一次；reverse区间反转阶段每个节点恰好被处理一次；递归拼接也是线性扫描。整体线性完成，n 为链表长度。
• 空间复杂度：本题目的严格约束是"常数级额外内存"，但递归实现本身会占用 O(n/k) 的调用栈空间（每层递归处理 k 个节点）。这一点值得注意：若面试场景严格要求 O(1) 空间，可将该递归框架改写为迭代版本（如借助 dummy 头节点 + 每次先探测 k 个节点再局部反转的循环），思路与本实现完全同构；本仓库的递归版本以可读性和简洁性见长，与 Problem 24 的迭代实现 形成了"同一问题两种风格"的对照素材。

与 Problem 24 的横向对比

对比两题在仓库中的实现，可以更直观地体会"特例 vs 一般化"：

• Problem 24 实现 采用dummy哨兵节点 + 单循环迭代，通过一次多重赋值同时完成四个指针的交换，代码极为紧凑，但步长固定为 2；
• 本题把步长泛化为 k，无法再用"固定四指针"的写法，于是仓库选择了递归切割方案：每次只负责反转"当前这 k 个"，剩余部分交给递归，逻辑边界清晰，与题目"按组处理"的语义天然吻合。

对于链表类问题，"特例写法高效、一般化写法递归"是一对很典型的取舍，读者可结合两题的源码与测试对比研读。

边界情况小结

1. k = 1：每段只有一个节点，探路直接返回，链表不变（测试已覆盖）；
2. 链表长度恰好是 k 的整数倍：最后一组也参与反转，node走 k 步后为nil，递归以nil为基底正常收束；
3. 末尾余数不足 k：探路在途中遇到nil，该段原样返回（示例k = 3, [4,5]即属此类）；
4. 空链表 / k 大于链表长度：首次探路即返回head（即nil），无需特殊处理。

小结

本文以原题解文档为骨架，完整还原了 LeetCode 25 的题意、约束、示例与"递归 + 区间反转"的解题思路，并结合仓库源码逐行剖析了reverseKGroup与reverse两个函数的实现细节、测试用例的构造方式及复杂度特征。核心可复用要点有三：一是"先探 k 步再决定是否反转"的探路模式，二是"左闭右开区间 + prev 初始化为区间外节点"的区间反转技巧，三是"段尾接递归结果"的递归切割框架。掌握这套三板斧，类似"K 个一组做 XX 操作"的链表题都可以快速套用。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go