示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文基于 doocs/leetcode 仓库中 第 25 题题解英文版系统讲解 K 个一组翻转链表Reverse Nodes in k-Group的题意、约束与关键陷阱完整拆解“探测—断开—翻转—重连”的模拟法实现并结合仓库中 Python、Java、C、Go、TypeScript、Rust、C#、PHP 八种语言的官方题解源码剖析指针写操作在边界处理上的易错点读完后你可以独立完成这道困难题并满足 O(1) 额外空间的 Follow-up 要求。一、题目定义与约束条件题目要求给定链表头节点head每k个节点一组进行翻转返回修改后的链表。其中k是正整数且k不超过链表长度若剩余节点数不是k的整数倍末尾不足k个的节点保持原有顺序不发生改变不允许修改节点中的值val只允许改变节点本身的指针连接。官方题解给出两个示例与仓库 images 目录中的配图一一对应示例 1head [1,2,3,4,5],k 2→ 输出[2,1,4,3,5]示例 2head [1,2,3,4,5],k 3→ 输出[3,2,1,4,5]约束条件Constraints约束项范围节点总数n1 k n 5000节点值Node.val0 Node.val 1000Follow-up能否使用O(1)的额外内存空间解决该问题这一追问直接决定了方案选型——这也是仓库题解“Thinking”部分首先分析的出发点最直觉的做法是按组递归翻k个节点然后对剩余部分递归。考虑到n 5000递归方案可以顺利通过但递归调用栈的深度随“组数”增长最坏n/k层无法满足O(1)额外空间的追问要求。因此仓库题解选择了纯模拟的迭代方案只使用常数个指针变量完成全部操作。二、思路剖析两个易错点与三个动作仓库题解的思考框架Thinking明确指出了本算法两个最容易出错的环节必须确认一个完整的k组若不足k个节点必须原样保留尾部不能部分翻转翻转后的片段必须完整“缝合”回原链表断开与重连过程中任何一次指针丢失都会导致链表断裂或成环。围绕这两个易错点题解把整个算法归纳为循环内的三个动作——探测Probe、翻转Reverse、重连Relink维护一个虚拟头节点dummy和一个“上一组的尾节点”指针pre初始都指向链表起点之前每轮循环从pre出发向前走k步进行探测如果中途走出None说明剩余不足一组直接返回dummy.next尾部保持原样探测成功则记录四个关键指针本组头node pre.next、本组尾cur、下一组头nxt cur.next将cur.next置空把长度为k的独立子链表交给reverse函数整体翻转翻转后pre.next指向新的组头原组头node翻转后变成组尾接上nxt然后把pre推进到node进入下一轮循环。由于“探测、翻转、重连”全部是指针写操作没有创建数组或递归栈额外空间就是常数级O(1)正好回应 Follow-up。三、解法一模拟法Simulation仓库题解给出的解法名为Solution 1: Simulation核心思想是“完全按照题目描述模拟整个翻转过程”具体分四步定义辅助函数reverse实现普通单链表翻转这里采用的是“头插法”每个节点依次插入到 dummy 头部时间O(k)额外O(1)节点定义虚拟头节点dummy令其next指向head用pre统一追踪“上一处理组的尾节点”每次处理k个节点剩余不足k个则不翻转、直接结束否则摘出这k个节点调用reverse翻转再把翻转后的链表接回原链表继续处理下一组直到整个链表遍历完毕。时间复杂度O(n)每个节点至多被翻转操作访问一次探测阶段也是线性步数空间复杂度O(1)。下面按仓库源码逐语言给出实现代码与 Solution.py 等文件完全一致可直接复制运行。3.1 Python3# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def reverseKGroup(self, head: Optional[ListNode], k: int) - Optional[ListNode]: def reverse(head: Optional[ListNode]) - Optional[ListNode]: dummy ListNode() cur head while cur: nxt cur.next cur.next dummy.next dummy.next cur cur nxt return dummy.next dummy pre ListNode(nexthead) while pre: cur pre for _ in range(k): cur cur.next if cur is None: return dummy.next node pre.next nxt cur.next cur.next None pre.next reverse(node) node.next nxt pre node return dummy.next逐行对照源码说明几个关键写操作dummy pre ListNode(nexthead)dummy与pre初始指向同一节点pre是“上一组尾”游标翻转完成后推进到当前组尾pre node探测循环for _ in range(k): cur cur.next一旦cur is None就return dummy.next此时尾部不足一组前面的修改已经全部完成直接收尾node pre.next必须在翻转前保存——翻转后它从组头变成组尾是“重连”阶段的关键锚点cur.next None先把本组与后文断开reverse只需处理长度恰为k的独立子链避免反转时把后续节点也卷进去pre.next reverse(node)接上新组头node.next nxt用原组尾接回下一组头一次完成缝合。3.2 Java/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode reverseKGroup(ListNode head, int k) { ListNode dummy new ListNode(0, head); dummy.next head; ListNode pre dummy; while (pre ! null) { ListNode cur pre; for (int i 0; i k; i) { cur cur.next; if (cur null) { return dummy.next; } } ListNode node pre.next; ListNode nxt cur.next; cur.next null; pre.next reverse(node); node.next nxt; pre node; } return dummy.next; } private ListNode reverse(ListNode head) { ListNode dummy new ListNode(); ListNode cur head; while (cur ! null) { ListNode nxt cur.next; cur.next dummy.next; dummy.next cur; cur nxt; } return dummy.next; } }Java 版中reverse同样使用 dummy 头插法注意cur.next null对应 Java 的cur.next null写法ListNode(0, head)构造后再次显式dummy.next head是源码中的双保险写法。3.3 C/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode* dummy new ListNode(0, head); ListNode* pre dummy; while (pre ! nullptr) { ListNode* cur pre; for (int i 0; i k; i) { cur cur-next; if (cur nullptr) { return dummy-next; } } ListNode* node pre-next; ListNode* nxt cur-next; cur-next nullptr; pre-next reverse(node); node-next nxt; pre node; } return dummy-next; } private: ListNode* reverse(ListNode* head) { ListNode* dummy new ListNode(); ListNode* cur head; while (cur ! nullptr) { ListNode* nxt cur-next; cur-next dummy-next; dummy-next cur; cur nxt; } return dummy-next; } };C 版结构与 Python/Java 完全同构指针判空写作 nullptr。dummy由new ListNode(0, head)动态分配是 LeetCode 判题环境下的常见写法判题结束即回收。3.4 Go/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func reverseKGroup(head *ListNode, k int) *ListNode { dummy : ListNode{Next: head} pre : dummy for pre ! nil { cur : pre for i : 0; i k; i { cur cur.Next if cur nil { return dummy.Next } } node : pre.Next nxt : cur.Next cur.Next nil pre.Next reverse(node) node.Next nxt pre node } return dummy.Next } func reverse(head *ListNode) *ListNode { var dummy *ListNode cur : head for cur ! nil { nxt : cur.Next cur.Next dummy dummy cur cur nxt } return dummy }Go 版有一个细节值得注意这里的reverse采用的是prev迭代翻转的变体cur.Next dummy; dummy cur返回的dummy直接就是翻转后的新头比“头插 dummy 节点”少建了一个节点空间上更紧凑。3.5 TypeScript/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } * } */ function reverseKGroup(head: ListNode | null, k: number): ListNode | null { const dummy new ListNode(0, head); let pre dummy; while (pre ! null) { let cur: ListNode | null pre; for (let i 0; i k; i) { cur cur?.next || null; if (cur null) { return dummy.next; } } const node pre.next; const nxt cur?.next || null; cur!.next null; pre.next reverse(node); node!.next nxt; pre node!; } return dummy.next; } function reverse(head: ListNode | null): ListNode | null { let dummy: ListNode | null null; let cur head; while (cur ! null) { const nxt cur.next; cur.next dummy; dummy cur; cur nxt; } return dummy; }TypeScript 版由于类型系统无法自动收窄cur?.next的结果使用了cur?.next || null与cur!断言来保证空值处理明确语义上与其他语言完全一致。3.6 Rust所有权视角的变体Rust 版的实现思路相同但从源码结构看它因所有权模型采用了不同的指针推进方式// Definition for singly-linked list. // #[derive(PartialEq, Eq, Clone, Debug)] // pub struct ListNode { // pub val: i32, // pub next: OptionBoxListNode // } // // impl ListNode { // #[inline] // fn new(val: i32) - Self { // ListNode { // next: None, // val // } // } // } impl Solution { pub fn reverse_k_group(head: OptionBoxListNode, k: i32) - OptionBoxListNode { fn reverse(head: OptionBoxListNode) - OptionBoxListNode { let mut head head; let mut pre None; while let Some(mut node) head { head node.next.take(); node.next pre.take(); pre Some(node); } pre } let mut dummy Some(Box::new(ListNode::new(0))); let mut pre mut dummy; let mut cur head; while cur.is_some() { let mut q mut cur; for _ in 0..k - 1 { if q.is_none() { break; } q mut q.as_mut().unwrap().next; } if q.is_none() { pre.as_mut().unwrap().next cur; return dummy.unwrap().next; } let b q.as_mut().unwrap().next.take(); pre.as_mut().unwrap().next reverse(cur); while pre.is_some() pre.as_mut().unwrap().next.is_some() { pre mut pre.as_mut().unwrap().next; } cur b; } dummy.unwrap().next } }与其他语言对比Rust 版的差异点reverse使用take()转移所有权来完成指针重接while let Some(mut node) head在移动节点的同时把head推进到下一节点等价于经典的prev迭代翻转探测时用q沿OptionBoxListNode的next字段推进k-1步一旦None提前break因为Option字段被整体移动pre.as_mut().unwrap().next reverse(cur)之后pre指向的Option已不是原来的Option内容代码通过“向下走到新链尾”的 while 循环把pre重新定位到翻转后链表的尾节点这正是“重连”步骤在所有权语义下的等价实现let b q.as_mut().unwrap().next.take()在翻转前摘出下一段cur b继续处理剩余部分。从源码结构看虽然写法与 C 有差异但“探测 → 断开 → 翻转 → 重连”的控制流完全一致且同样是纯指针操作额外空间O(1)。3.7 C#/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val 0, ListNode next null) { * this.val val; * this.next next; * } * } */ public class Solution { public ListNode ReverseKGroup(ListNode head, int k) { var dummy new ListNode(0); dummy.next head; var pre dummy; while (pre ! null) { var cur pre; for (int i 0; i k; i) { if (cur.next null) { return dummy.next; } cur cur.next; } var node pre.next; var nxt cur.next; cur.next null; pre.next Reverse(node); node.next nxt; pre node; } return dummy.next; } private ListNode Reverse(ListNode head) { ListNode prev null; var cur head; while (cur ! null) { var nxt cur.next; cur.next prev; prev cur; cur nxt; } return prev; } }C# 版有两处风格差异探测循环把判空放在cur.next null先检查再前进Reverse采用经典prev迭代写法而非 dummy 头插法——两者只是局部翻转的实现变体对整体复杂度没有影响。3.8 PHP/** * Definition for a singly-linked list. * class ListNode { * public $val 0; * public $next null; * function __construct($val 0, $next null) { * $this-val $val; * $this-next $next; * } * } */ class Solution { /** * param ListNode $head * param Integer $k * return ListNode */ function reverseKGroup($head, $k) { $dummy new ListNode(0); $dummy-next $head; $pre $dummy; while ($pre ! null) { $cur $pre; for ($i 0; $i $k; $i) { if ($cur-next null) { return $dummy-next; } $cur $cur-next; } $node $pre-next; $nxt $cur-next; $cur-next null; $pre-next $this-reverse($node); $node-next $nxt; $pre $node; } return $dummy-next; } /** * Helper function to reverse a linked list. * param ListNode $head * return ListNode */ function reverse($head) { $prev null; $cur $head; while ($cur ! null) { $nxt $cur-next; $cur-next $prev; $prev $cur; $cur $nxt; } return $prev; } }PHP 版与 C# 版同源探测时先检查$cur-next null局部翻转用prev迭代写法。四、指针操作逐步推演以示例 1 为例结合head [1,2,3,4,5]、k 2手动走一遍 Solution.py 的逻辑有助于确认每一步指针状态初始dummy - 1 - 2 - 3 - 4 - 5 - Nonepre dummy。第 1 轮从pre走k2步cur停在节点 2node 1组头nxt 3下一组头cur.next None断开2 - 3得到独立子链1 - 2reverse(1)节点 1、2 依次头插结果为2 - 1pre.next 2node.next nxt原组头 1 接上 3pre node 1。链表状态dummy - 2 - 1 - 3 - 4 - 5。第 2 轮从pre1走 2 步cur停在节点 4node 3nxt 5断开、翻转子链3 - 4得4 - 3接回后3 - 5pre 3。链表状态dummy - 2 - 1 - 4 - 3 - 5。第 3 轮从pre3走 2 步第二步时cur变为None剩余只有节点 5 一个触发return dummy.next尾部5保持原样最终返回2 - 1 - 4 - 3 - 5与示例输出[2,1,4,3,5]一致。k 3时同理第一组1-2-3翻转为3-2-1剩余4-5不足 3 个保持原序得到[3,2,1,4,5]。五、复杂度分析与 Follow-up 回应时间复杂度O(n)。设链表长度为n。探测阶段每个节点最多被cur走过一次翻转阶段每个节点恰好参与一次局部翻转每组O(k)共n/k组合计O(n)。两者相加仍是线性。空间复杂度O(1)。全程只使用dummy、pre、cur、node、nxt等固定数量的指针变量reverse内部也只有常数指针没有额外数组也没有递归调用栈因此满足 Follow-up 中O(1)额外空间的追问。作为对照仓库题解也提到过按组递归的备选思路递归版代码更简洁但栈深随组数n/k增长最坏可达nk1时额外空间退化为O(n)这就是本仓库选择模拟迭代法的原因。六、易错点清单与验证建议基于题解“Thinking”部分与源码实现可以归纳出四个最常见的错误模式供调试时自查忘记保存node pre.next翻转之后原组头已变成组尾不提前保存就无法执行node.next nxt的尾部重连导致断链翻转前未将cur.next置空reverse会沿着next一直翻到链表末尾把本不该动的尾部节点一起翻转违反“剩余不足 k 个保持原样”的要求探测步数写错for循环必须恰好走k步走少一步会把下一组的第一个节点卷进当前组走多一步则组间重叠pre推进错误每轮结束后必须pre node翻转后的组尾否则下一轮会重复处理同一组形成死循环。验证方式可以用k 1应完全不变、k n整体翻转、n % k 1尾部恰剩 1 个三类边界输入自测仓库中每题目录下的Solution.py/Solution.java等文件即可配合任意 LeetCode 判题环境运行。七、在仓库中的位置与相关题解本题位于仓库solution目录第 0000–0099 区段目录结构为 solution/0000-0099/0025.Reverse Nodes in k-Group含中英文 README 与八语言 Solution 文件在 总题解索引 中登记为题号0025标题「K 个一组翻转链表」标签递归、链表难度「困难」。与本题同属“链表局部翻转”主题的仓库相关题解建议按以下顺序巩固两两交换链表中的节点第 24 题k2的简化版掌握虚拟头节点 局部重连的基本功删除链表的倒数第 N 个结点第 19 题双指针定位与断链重连的基础训练。掌握“探测—断开—翻转—重连”这一套固定套路后第 24、25 题乃至后续更大组长的变体都可以用同一框架推导实现。赞分享示例工程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐doocs/leetcode 题解精讲LeetCode 25 每 k 个节点一组翻转链表的 O(1) 空间模拟解法doocs/leetcode 题解精讲LeetCode 25 每 k 个节点一组翻转链表的 O 1 空间模拟解法 本文围绕 doocs/leetcode 仓库示例工程LeetCode 25「K 个一组翻转链表」双解法全解递归与迭代的指针操控艺术LeetCode 25「K 个一组翻转链表」双解法全解递归与迭代的指针操控艺术 本篇技术指南围绕 LeetCode 25 号题 Reverse Nodes i示例工程一套代码驱动五类飞行器ArduPilot 开源飞控完整指南一套代码驱动五类飞行器ArduPilot 开源飞控完整指南 ArduPilot 是一套成熟的开源飞控系统同一份代码同时驱动多旋翼、固定翼、地面车、水下机器人嵌入式无人机自动驾驶机器人固件上一篇5步实现Unity模组高效管理零基础轻松上手的实用指南下一篇MeshGen远程API配置教程Hugging Face、Anthropic与OpenAI无缝集成创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考