LeetCode-Go 题解实战LeetCode 92 反转链表 II 的 Go 实现与头插法一次遍历详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇基于 LeetCode-Go 仓库中 LeetCode 92 题解文档完整还原反转链表从位置 m 到 n这道经典链表题的题目要求与一次遍历one-pass的头插法解题思路并结合仓库中真实的 Go 解法 92. Reverse Linked List II.go 与测试用例 92. Reverse Linked List II_test.go逐行拆解指针操作与循环控制逻辑读完你可以掌握哑头结点dummy node如何消除边界特判、头插法如何用恰好n-m次循环完成区间反转、以及如何用仓库内置的链表工具函数编写可复现的表驱动测试。题目描述与约束LeetCode 92Reverse Linked List II的原题要求Reverse a linked list from position m to n. Do it in one-pass.Note: 1 ≤ m ≤ n ≤ length of list.题目大意给定链表中两个结点的位置 m 和 n反转这两个位置区间内的所有结点且要求一次遍历完成。官方示例Input: 1-2-3-4-5-NULL, m 2, n 4 Output: 1-4-3-2-5-NULL即把第 2 到第 4 个结点2-3-4原地反转为4-3-2区间外的1与5保持不动。约束条件1 ≤ m ≤ n ≤ 链表长度意味着需要处理的区间至少包含一个结点且区间一定合法存在但区间可能从头结点开始m 1这是最容易写错的边界。解题思路哑头结点 头插法原始题解文档给出的核心思路可以概括为三步构造新的头结点由于有可能整个链表都被反转例如 m 1直接操作原头结点会使头结点本身参与反转边界处理非常繁琐。因此先构造一个哑头结点dummy head指向当前头结点之后的所有操作都基于这个固定的入口进行返回值取newHead.Next即可统一覆盖反转区间含头部与不含头部两种情况。定位区间前驱找到第一个需要反转的结点的前一个结点p即第 m-1 个结点。从这里开始把p后面的结点逐个摘下来用头插法插到p结点后面。循环次数用n - m控制区间长度是n - m 1个结点而头插法每执行一次就把当前区间头部第一个结点挪到区间最前面只需n - m次即可完成整个区间的反转。这里有一个仓库题解中特别强调的细节值得单独说明这一题结点可以原地变化更改各个结点的 next 指针就可以。不需要游标 p 指针移动。因为每次逆序以后原有结点的相对位置就发生了变化相当于游标指针已经移动了所以不需要再有游标 p p.Next 的操作了。换言之pre指针在定位到第 m-1 个结点后就固定不动反转全部通过pre之后一段链上的指针重排完成——这是本解法区别于先翻转再缝合两段式写法的关键也保证了严格的一次遍历。Go 实现逐行解析仓库中的完整解法位于 92. Reverse Linked List II.go函数签名为reverseBetween(head *ListNode, m int, n int) *ListNode链表节点类型通过别名复用仓库公共结构体包 structures/ListNode.go 中的定义// ListNode 是链接节点 type ListNode struct { Val int Next *ListNode }题解代码如下保留原始实现func reverseBetween(head *ListNode, m int, n int) *ListNode { if head nil || m n { return head } newHead : ListNode{Val: 0, Next: head} pre : newHead for count : 0; pre.Next ! nil count m-1; count { pre pre.Next } if pre.Next nil { return head } cur : pre.Next for i : 0; i n-m; i { tmp : pre.Next pre.Next cur.Next cur.Next cur.Next.Next pre.Next.Next tmp } return newHead.Next }逐段拆解① 边界保护与哑头结点第 1923 行head nil直接返回避免空指针m n时区间长度为 0 或退化按题目约束m ≤ n仅在m n时成立单结点反转即自身原样返回即可newHead : ListNode{Val: 0, Next: head}构造哑头结点Val: 0仅作占位不参与任何计算。② 定位第 m-1 个结点第 2429 行for count : 0; pre.Next ! nil count m-1; count { pre pre.Next }从哑头结点出发走m-1步。循环里pre.Next ! nil的防御条件覆盖了测试集中m越界类的脏输入见下文测试用例[]int{3}, 3, 5当pre.Next nil时说明链表在到达 m 之前已经走完无需反转直接返回原头。③ 头插法反转循环第 3036 行cur : pre.Next for i : 0; i n-m; i { tmp : pre.Next pre.Next cur.Next cur.Next cur.Next.Next pre.Next.Next tmp }这是全篇最精妙的四行指针操作。设初始状态为pre - cur - B - C - ...cur是区间内第一个结点B是第二个步骤语句作用1tmp : pre.Next暂存当前区间头部结点cur防止断链后丢失2pre.Next cur.Next把cur从区间头部摘除pre改指向B3cur.Next cur.Next.Next把cur的Next越过B为最后插回腾位B是区间第一个时其Next可能为nil语句依然安全4pre.Next.Next tmp把cur重新挂在区间最前完成一次头插一次迭代后状态变为pre - B - cur - C - ...即把原来的第一个结点挪到了当前已处理的区间末尾方向。由于pre固定每次迭代总是操作当前pre.Next因此循环体内没有任何指针移动恰好印证了题解文档不需要游标 p p.Next 操作的论述。重复n-m次后区间内n-m1个结点全部倒序。以官方示例1-2-3-4-5, m2, n4手动推演初始: pre(哑) - 1 - 2 - 3 - 4 - 5 cur2 第1轮: 摘 2 插到 1 后区间前 → 1 - 3 - 2 - 4 - 5 第2轮: 摘 3 插到前 → 1 - 4 - 3 - 2 - 5共n-m 2轮得到1-4-3-2-5与题目输出一致。④ 返回值第 37 行return newHead.Next统一返回真正的头无论 m 是否为 1反转后的新头都由哑头结点的Next给出这正是引入哑头结点的全部价值。从源码结构看该实现整体时间复杂度为 O(n)定位 O(m) 反转 O(n-m)m ≤ n空间复杂度 O(1)严格满足 one-pass 要求。表驱动测试与运行验证仓库为该题配置了标准表驱动测试 92. Reverse Linked List II_test.go测试结构体分为para92入参数组 m n与ans92期望输出的数组。共 6 组用例针对性覆盖了实现中的各个分支输入数组, m, n期望输出覆盖点{1,2,3,4,5}, 2, 4{1,4,3,2,5}官方标准示例区间在链表中部{1,2,3,4,5}, 2, 2{1,2,3,4,5}m n循环 0 次链表不变{1,2,3,4,5}, 1, 5{5,4,3,2,1}整个链表全部反转验证哑头结点处理 m 1 的能力{1,2,3,4,5,6}, 3, 4{1,2,4,3,5,6}区间长度为 2 的最小非平凡反转{3,5}, 1, 2{5,3}双结点链表、头结点参与反转{3}, 3, 5{3}m 越界触发pre.Next nil防御分支原样返回测试依赖仓库公共包 structures/ListNode.go 提供的两个转换工具Ints2List(nums []int) *ListNode把[]int构造成链表作为函数入参List2Ints(head *ListNode) []int把链表还原为[]int以便断言与打印且内置了 100 层深度保护——若遍历超过 100 个结点会直接panic防止解法错误产生环状链表导致测试死循环这点对链表题测试非常实用。在仓库根目录下可以单独运行本题测试go test -run Test_Problem92 ./leetcode/0092.Reverse-Linked-List-II/如果想验证全仓库的测试与 100% 覆盖率声明仓库提供了 gotest.sh 脚本其核心命令为go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...脚本注释中说明了使用单个合法 coverage profile 而非逐包追加的原因新版 Codecov 解析器对多段mode: atomic头会解析为 0% 覆盖率覆盖率结果落在仓库根目录的 coverage.txt。小结本题的关键在于两点哑头结点把区间是否包含头结点这一分支统一掉头插法 固定前驱指针用恰好n-m次纯指针重排完成一次遍历反转仓库解法中循环体tmp : pre.Next; pre.Next cur.Next; cur.Next cur.Next.Next; pre.Next.Next tmp是标准的头插四步式可推广到其他把某结点从链中摘出并插到指定位置的链表操作测试层面structures包的Ints2List/List2Ints与深度保护机制让链表题的表驱动测试既简洁又能自动拦截环状链错误这一模式在仓库其余链表题如 0206、0234中均可见复用。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考