企业官网建设流程全解析

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-Go

LeetCode-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 = 4，Output: 1->4->3->2->5->NULL。

用 仓库内的中文题解 README 一句话概括就是：给定链表中两个节点的位置m, n，反转这两个位置区间内的所有节点。

从约束可以看出两个必须处理的难点：

1. m可能等于 1：反转区间包含头节点，反转后链表头会变化，需要一个"永远存在的左端锚点"；
2. 反转区间可能很短甚至退化（m == n时无需反转），算法在任意长度区间下都必须正确。

解法核心：dummy 头节点 + 头插法

英文题解文档 给出的思路是：

由于有可能整个链表都被反转，所以构造一个新的头结点指向当前的头。之后的处理方法是：找到第一个需要反转的结点的前一个结点p，从这个结点开始，依次把后面的结点用"头插"法插入到p结点的后面。循环次数用n-m来控制。

对应的完整实现（见 92. Reverse Linked List II.go）：

func 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写任何特判分支。

第二步：定位前驱节点pre

for 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的用例（单节点链表却传入m=3, n=5），靠的就是这个保护逻辑让原链表安全原样返回，而不是在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 -> 1，cur = 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 仍引用节点2，2.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 组用例，覆盖了该算法需要防守的全部边界：

测试通过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