LeetCode-Go 中第 92 题「Reverse Linked List II」的一次遍历区间反转解法头插法指针技巧详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-GoLeetCode-Go 仓库为 LeetCode 第 92 题Reverse Linked List II反转链表 II提供了一种基于头插法的单遍one-pass原地解法只需找到待反转区间前一个节点随后循环n - m次将后续节点逐个摘出并插到它后面即可完成 m 到 n 位置节点的逆序。读完本文你能理解 dummy 头节点为何必要、四行指针修改为何无需额外游标指针并能结合 实现源码 与 测试用例 独立验证每一类边界情况。题目描述与核心约束原题要求将单链表中从位置m到n之间的节点反转且要求一次性遍历Do it in one-pass。题目自带约束1 ≤ m ≤ n ≤ length of list示例Input: 1-2-3-4-5-NULL, m 2, n 4Output: 1-4-3-2-5-NULL。用 仓库内的中文题解 README 一句话概括就是给定链表中两个节点的位置m, n反转这两个位置区间内的所有节点。从约束可以看出两个必须处理的难点m可能等于 1反转区间包含头节点反转后链表头会变化需要一个永远存在的左端锚点反转区间可能很短甚至退化m n时无需反转算法在任意长度区间下都必须正确。解法核心dummy 头节点 头插法英文题解文档 给出的思路是由于有可能整个链表都被反转所以构造一个新的头结点指向当前的头。之后的处理方法是找到第一个需要反转的结点的前一个结点p从这个结点开始依次把后面的结点用头插法插入到p结点的后面。循环次数用n-m来控制。对应的完整实现见 92. Reverse Linked List II.gofunc reverseBetween(head *ListNode, m int, n int) *ListNode { if head nil || m n { return head } newHead : ListNode{Val: 0, Next: head} // dummy 头节点 pre : newHead for count : 0; pre.Next ! nil count m-1; count { pre pre.Next // 定位到第 m 个节点的前驱 } 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 }这段代码可以分为三个部分边界过滤、区间定位、头插反转。下面逐一拆解。第一步边界过滤与 dummy 节点head nil空链表直接返回m n区间长度不足两个节点无需反转直接返回注意题目约束m ≤ n所以实际命中的是m n的退化情形newHead : ListNode{Val: 0, Next: head}构造 dummy 头节点。这是区间可能从头节点开始反转这一难点的解法——让pre的初始值指向 dummy 节点而非真实头节点当m 1时pre就正好停在 dummy 上反转结束后通过return newHead.Next统一取回新头全程不需要对m 1写任何特判分支。第二步定位前驱节点prefor count : 0; pre.Next ! nil count m-1; count { pre pre.Next } if pre.Next nil { return head }循环恰好走m - 1步使pre停在第m个节点的前一个节点。注意循环条件里带了pre.Next ! nil的短路保护并且循环结束后再次检查pre.Next nil这是为了防御测试数据中n超出链表实际长度的情况——仓库的 测试文件 里恰好有一个[]int{3}, m 3, n 5的用例单节点链表却传入m3, n5靠的就是这个保护逻辑让原链表安全原样返回而不是在cur.Next上解引用空指针。第三步四行指针修改完成一次头插核心循环每次迭代只修改 4 个指针把pre后面的第一个节点tmp摘下来、插到pre之后并让cur越过被移动的节点for i : 0; i n-m; i { tmp : pre.Next // tmp 是 pre 后面第一个节点将被移动到 pre 之后 pre.Next cur.Next // pre 越过 cur指向 cur 的后继 cur.Next cur.Next.Next // cur 的后继跳两格保持区间第一个节点的身份 pre.Next.Next tmp // 把 tmp 插到 pre 之后tmp 指向原 pre.Next }这里最关键的设计是pre在整个反转过程中纹丝不动cur的引用值也不变它始终指向当前反转区间的第一个节点变化的是它们背后的Next指向。英文题解对此有一段精到的解释这一题结点可以原地变化更改各个结点的 next 指针就可以。不需要游标p指针。因为每次逆序以后原有结点的相对位置就发生了变化相当于游标指针已经移动了所以不需要再有游标p p.Next的操作了。换句话说头插法本身让区间头部自动向后滑动省掉了常规链式遍历中维护移动游标的麻烦也天然保证了单次遍历完成。图解一次完整执行过程以测试用例1-2-3-4-5、m 2, n 4为例逐步跟踪指针pre初始为 dummy定位后pre - 1cur 2待反转区间为2-3-4循环执行n - m 2次。迭代前: dummy - 1 - 2 - 3 - 4 - 5 pre cur第 1 次迭代把节点 2 插到 1 后面——此时 2 本来就在 1 后面实际是把 2 与 3 的相对顺序翻转迭代前: 1 - 2 - 3 - 4 - 5 pre cur 第1行: tmp 2 第2行: pre.Next 3 1 - 3 第3行: cur.Next 4 cur 仍引用节点22.Next 改为指向 4 第4行: 3.Next tmp(2) 3 - 2 结果: 1 - 3 - 2 - 4 - 5 pre cur第 2 次迭代把节点 3 插到 1 后面迭代前: 1 - 3 - 2 - 4 - 5 pre cur 第1行: tmp 3 第2行: pre.Next 2 1 - 2 第3行: cur.Next 4 3.Next 改为指向 4 第4行: 2.Next tmp(3) 2 - 3 结果: 1 - 4 - 3 - 2 - 5 pre cur循环恰好执行n - m 2次后结束返回newHead.Next即1-4-3-2-5-NULL与题目输出一致。整个过程pre从未移动所有变化都发生在Next指针上——这正是文档强调不需要游标指针移动的含义。边界用例与源码实现的对齐仓库测试文件 92. Reverse Linked List II_test.go 使用question92表驱动结构构造了 6 组用例覆盖了该算法需要防守的全部边界用例期望输出验证的边界[1,2,3,4,5], m2, n4[1,4,3,2,5]标准中途区间反转[1,2,3,4,5], m2, n2[1,2,3,4,5]m n退化区间命中m n提前返回[1,2,3,4,5], m1, n5[5,4,3,2,1]反转整个链表头节点变化验证 dummy 节点的必要性[1,2,3,4,5,6], m3, n4[1,2,4,3,5,6]长度为 2 的最小有效区间[3,5], m1, n2[5,3]m 1时pre初始即 dummy无特判也能正确处理[3], m3, n5[3]n超出链表长度验证pre.Next nil保护逻辑测试通过structures.Ints2List把切片转成链表、再经structures.List2Ints转回切片进行比对。这两个工具函数定义在 structures/ListNode.go其中List2Ints还内置了 100 层深度上限的环检测超过会 panic相当于在测试输出环节兜底防止反转把链表变成环的隐蔽错误。题解文件中使用的ListNode也通过type ListNode structures.ListNode别名统一复用该公共定义保证题目代码与 数据结构定义Val int/Next *ListNode单一来源。复杂度与适用前提时间复杂度定位pre走m - 1步反转循环固定n - m步合计n - 1次指针操作为O(n)且只走一遍链表满足题目 one-pass 要求空间复杂度除一个 dummy 节点外全部原地修改Next指针O(1)适用前提输入满足1 ≤ m ≤ n ≤ length of list。源码中的pre.Next nil保护使其在测试数据n越界时也能安全返回原链表属于防御性实现而非题目约束内的常规路径。与先反转 m~n 区间再整体反转的两段式写法相比本仓库采用的头插法用一个静止的锚点pre和固定不变的身份指针cur完成了区间逆序代码量更少、分支更少而 dummy 节点的设计则把m 1这一最容易出错的场景吸收进了统一的循环逻辑中这正是这套写法在 仓库题解文档 中被强调的两个设计意图。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Go 中第 92 题「Reverse Linked List II」的一次遍历区间反转解法：头插法指针技巧详解
LeetCode-Go 中第 92 题「Reverse Linked List II」的一次遍历区间反转解法头插法指针技巧详解【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-GoLeetCode-Go 仓库为 LeetCode 第 92 题Reverse Linked List II反转链表 II提供了一种基于头插法的单遍one-pass原地解法只需找到待反转区间前一个节点随后循环n - m次将后续节点逐个摘出并插到它后面即可完成 m 到 n 位置节点的逆序。读完本文你能理解 dummy 头节点为何必要、四行指针修改为何无需额外游标指针并能结合 实现源码 与 测试用例 独立验证每一类边界情况。题目描述与核心约束原题要求将单链表中从位置m到n之间的节点反转且要求一次性遍历Do it in one-pass。题目自带约束1 ≤ m ≤ n ≤ length of list示例Input: 1-2-3-4-5-NULL, m 2, n 4Output: 1-4-3-2-5-NULL。用 仓库内的中文题解 README 一句话概括就是给定链表中两个节点的位置m, n反转这两个位置区间内的所有节点。从约束可以看出两个必须处理的难点m可能等于 1反转区间包含头节点反转后链表头会变化需要一个永远存在的左端锚点反转区间可能很短甚至退化m n时无需反转算法在任意长度区间下都必须正确。解法核心dummy 头节点 头插法英文题解文档 给出的思路是由于有可能整个链表都被反转所以构造一个新的头结点指向当前的头。之后的处理方法是找到第一个需要反转的结点的前一个结点p从这个结点开始依次把后面的结点用头插法插入到p结点的后面。循环次数用n-m来控制。对应的完整实现见 92. Reverse Linked List II.gofunc reverseBetween(head *ListNode, m int, n int) *ListNode { if head nil || m n { return head } newHead : ListNode{Val: 0, Next: head} // dummy 头节点 pre : newHead for count : 0; pre.Next ! nil count m-1; count { pre pre.Next // 定位到第 m 个节点的前驱 } 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 }这段代码可以分为三个部分边界过滤、区间定位、头插反转。下面逐一拆解。第一步边界过滤与 dummy 节点head nil空链表直接返回m n区间长度不足两个节点无需反转直接返回注意题目约束m ≤ n所以实际命中的是m n的退化情形newHead : ListNode{Val: 0, Next: head}构造 dummy 头节点。这是区间可能从头节点开始反转这一难点的解法——让pre的初始值指向 dummy 节点而非真实头节点当m 1时pre就正好停在 dummy 上反转结束后通过return newHead.Next统一取回新头全程不需要对m 1写任何特判分支。第二步定位前驱节点prefor count : 0; pre.Next ! nil count m-1; count { pre pre.Next } if pre.Next nil { return head }循环恰好走m - 1步使pre停在第m个节点的前一个节点。注意循环条件里带了pre.Next ! nil的短路保护并且循环结束后再次检查pre.Next nil这是为了防御测试数据中n超出链表实际长度的情况——仓库的 测试文件 里恰好有一个[]int{3}, m 3, n 5的用例单节点链表却传入m3, n5靠的就是这个保护逻辑让原链表安全原样返回而不是在cur.Next上解引用空指针。第三步四行指针修改完成一次头插核心循环每次迭代只修改 4 个指针把pre后面的第一个节点tmp摘下来、插到pre之后并让cur越过被移动的节点for i : 0; i n-m; i { tmp : pre.Next // tmp 是 pre 后面第一个节点将被移动到 pre 之后 pre.Next cur.Next // pre 越过 cur指向 cur 的后继 cur.Next cur.Next.Next // cur 的后继跳两格保持区间第一个节点的身份 pre.Next.Next tmp // 把 tmp 插到 pre 之后tmp 指向原 pre.Next }这里最关键的设计是pre在整个反转过程中纹丝不动cur的引用值也不变它始终指向当前反转区间的第一个节点变化的是它们背后的Next指向。英文题解对此有一段精到的解释这一题结点可以原地变化更改各个结点的 next 指针就可以。不需要游标p指针。因为每次逆序以后原有结点的相对位置就发生了变化相当于游标指针已经移动了所以不需要再有游标p p.Next的操作了。换句话说头插法本身让区间头部自动向后滑动省掉了常规链式遍历中维护移动游标的麻烦也天然保证了单次遍历完成。图解一次完整执行过程以测试用例1-2-3-4-5、m 2, n 4为例逐步跟踪指针pre初始为 dummy定位后pre - 1cur 2待反转区间为2-3-4循环执行n - m 2次。迭代前: dummy - 1 - 2 - 3 - 4 - 5 pre cur第 1 次迭代把节点 2 插到 1 后面——此时 2 本来就在 1 后面实际是把 2 与 3 的相对顺序翻转迭代前: 1 - 2 - 3 - 4 - 5 pre cur 第1行: tmp 2 第2行: pre.Next 3 1 - 3 第3行: cur.Next 4 cur 仍引用节点22.Next 改为指向 4 第4行: 3.Next tmp(2) 3 - 2 结果: 1 - 3 - 2 - 4 - 5 pre cur第 2 次迭代把节点 3 插到 1 后面迭代前: 1 - 3 - 2 - 4 - 5 pre cur 第1行: tmp 3 第2行: pre.Next 2 1 - 2 第3行: cur.Next 4 3.Next 改为指向 4 第4行: 2.Next tmp(3) 2 - 3 结果: 1 - 4 - 3 - 2 - 5 pre cur循环恰好执行n - m 2次后结束返回newHead.Next即1-4-3-2-5-NULL与题目输出一致。整个过程pre从未移动所有变化都发生在Next指针上——这正是文档强调不需要游标指针移动的含义。边界用例与源码实现的对齐仓库测试文件 92. Reverse Linked List II_test.go 使用question92表驱动结构构造了 6 组用例覆盖了该算法需要防守的全部边界用例期望输出验证的边界[1,2,3,4,5], m2, n4[1,4,3,2,5]标准中途区间反转[1,2,3,4,5], m2, n2[1,2,3,4,5]m n退化区间命中m n提前返回[1,2,3,4,5], m1, n5[5,4,3,2,1]反转整个链表头节点变化验证 dummy 节点的必要性[1,2,3,4,5,6], m3, n4[1,2,4,3,5,6]长度为 2 的最小有效区间[3,5], m1, n2[5,3]m 1时pre初始即 dummy无特判也能正确处理[3], m3, n5[3]n超出链表长度验证pre.Next nil保护逻辑测试通过structures.Ints2List把切片转成链表、再经structures.List2Ints转回切片进行比对。这两个工具函数定义在 structures/ListNode.go其中List2Ints还内置了 100 层深度上限的环检测超过会 panic相当于在测试输出环节兜底防止反转把链表变成环的隐蔽错误。题解文件中使用的ListNode也通过type ListNode structures.ListNode别名统一复用该公共定义保证题目代码与 数据结构定义Val int/Next *ListNode单一来源。复杂度与适用前提时间复杂度定位pre走m - 1步反转循环固定n - m步合计n - 1次指针操作为O(n)且只走一遍链表满足题目 one-pass 要求空间复杂度除一个 dummy 节点外全部原地修改Next指针O(1)适用前提输入满足1 ≤ m ≤ n ≤ length of list。源码中的pre.Next nil保护使其在测试数据n越界时也能安全返回原链表属于防御性实现而非题目约束内的常规路径。与先反转 m~n 区间再整体反转的两段式写法相比本仓库采用的头插法用一个静止的锚点pre和固定不变的身份指针cur完成了区间逆序代码量更少、分支更少而 dummy 节点的设计则把m 1这一最容易出错的场景吸收进了统一的循环逻辑中这正是这套写法在 仓库题解文档 中被强调的两个设计意图。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考