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-5k 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 lists 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。本仓库给出的实现采用递归框架整体思路分三步探路探测 k 步从当前段头节点出发前进 k 步。若中途遇到nil说明剩余节点不足 k 个直接返回当前头节点这一段不反转。区间反转对head, node)这个左闭右开区间内的 k 个节点执行反转返回反转后的新头节点。递归拼接将反转后的段尾即原 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,2,3,4,5]3[3,2,1,4,5]恰好一组 3 个反转末尾不足 3 个保持原样[1,2,3,4,5]1[1,2,3,4,5]k 1 时每段只有一个节点链表完全不变边界退化第二个用例很有价值当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.gotype 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 个剩余部分交给递归逻辑边界清晰与题目按组处理的语义天然吻合。对于链表类问题特例写法高效、一般化写法递归是一对很典型的取舍读者可结合两题的源码与测试对比研读。边界情况小结k 1每段只有一个节点探路直接返回链表不变测试已覆盖链表长度恰好是 k 的整数倍最后一组也参与反转node走 k 步后为nil递归以nil为基底正常收束末尾余数不足 k探路在途中遇到nil该段原样返回示例k 3, [4,5]即属此类空链表 / 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/10 16:51:15 · 阅读 1.2k LeetCode 25. Reverse Nodes in k-Group 题解：Go 递归实现 K 个一组反转链表
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-5k 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 lists 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。本仓库给出的实现采用递归框架整体思路分三步探路探测 k 步从当前段头节点出发前进 k 步。若中途遇到nil说明剩余节点不足 k 个直接返回当前头节点这一段不反转。区间反转对head, node)这个左闭右开区间内的 k 个节点执行反转返回反转后的新头节点。递归拼接将反转后的段尾即原 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,2,3,4,5]3[3,2,1,4,5]恰好一组 3 个反转末尾不足 3 个保持原样[1,2,3,4,5]1[1,2,3,4,5]k 1 时每段只有一个节点链表完全不变边界退化第二个用例很有价值当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.gotype 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 个剩余部分交给递归逻辑边界清晰与题目按组处理的语义天然吻合。对于链表类问题特例写法高效、一般化写法递归是一对很典型的取舍读者可结合两题的源码与测试对比研读。边界情况小结k 1每段只有一个节点探路直接返回链表不变测试已覆盖链表长度恰好是 k 的整数倍最后一组也参与反转node走 k 步后为nil递归以nil为基底正常收束末尾余数不足 k探路在途中遇到nil该段原样返回示例k 3, [4,5]即属此类空链表 / 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考