你好，同学。欢迎来到 NOI 专题训练营。在掌握了基础的“全链表反转”后，今天我们要攻克它的进阶版——区间反转。

这道题在 NOI 序列数据结构中非常经典，因为它不仅考察你对指针的控制，还考察了你对 “边界处理” 和 “局部与整体连接” 的严谨性。

---

一、 题目描述 (NOI 风格)

【题目名称】 反转链表 II (Reverse Linked List II) 【时间限制】 1.0s 【内存限制】 256MB

【问题描述】 给你单链表的头指针 head 和两个整数 left 和 right ，其中 $1 \le left \le right \le n$（$n$ 为链表节点总数）。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

【输入格式】 第一行包含链表的各节点值，以空格隔开。 第二行包含两个整数 $left$ 和 $right$。

【输出格式】 输出反转区间后的链表序列。

【样例 1 输入】

1 2 3 4 5
2 4

【样例 1 输出】

1 4 3 2 5

【样例 2 输入】

5
1 1

【样例 2 输出】

5

【数据范围】

• 链表中节点数目为 $n$。
• $1 \le n \le 500$。
• $-500 \le Node.val \le 500$。
• $1 \le left \le right \le n$。
• 进阶要求：使用一趟扫描完成反转。

---

二、 预备知识点

1. 哨兵节点 (Dummy Node)：在处理链表首节点可能发生变化的题目（如 $left=1$）时，建立一个虚拟头节点可以极大简化逻辑判断。
2. 局部反转逻辑：如何只改变中间一段的指针，而不破坏前后的连接。
3. 头插法 (Head Insertion)：在区间反转中，通过不断将节点插入到区间起始位置的前面，实现一步到位的翻转。

---

三、 启发式教学：草稿纸上的推理过程

反转区间比全反转难在：你需要记住区间前后的“接头人”。

1. 图形化拆解

假设链表为：A -> B -> [C -> D -> E] -> F -> G，$left=3, right=5$。 我们要反转 [C, D, E]。

在草稿纸上标记四个关键点：

• pre：反转区间的前驱（节点 B）。
• start：反转区间的第一个节点（节点 C），反转后它将变成区间的尾部。
• curr：当前正在处理的节点。
• next：当前节点的下一个，防止断链。

2. 一趟扫描的“头插法”推演

不要尝试先把子链表截断再接回去，那样需要两趟扫描。尝试**“挪动”**：

初始状态：pre(B) -> start(C) -> next(D) -> E -> F

1. 第一步：把 D 摘出来，插到 B 后面。
   • C 指向 E (跳过 D)
   • D 指向 C (D 回头)
   • B 指向 D (B 接住 D)
   • 结果：B -> D -> C -> E -> F
2. 第二步：把 E 摘出来，插到 B 后面。
   • C 指向 F (跳过 E)
   • E 指向 D (E 回头接住现在的区间头)
   • B 指向 E (B 接住 E)
   • 结果：B -> E -> D -> C -> F

核心观察：在这个过程中，pre (B) 和 start (C) 的位置是固定的，我们只是不断把 start 后面那个节点搬到 pre 的后面。

---

四、 算法流程图 (一趟扫描逻辑)

为了避免 Mermaid 语法报错，我们用括号代替方括号，并简化符号。

graph TD
    Start("开始") --> CreateDummy("创建 Dummy 节点指向 head")
    CreateDummy --> LocatePre("移动 pre 指针 left-1 次-到达区间前驱")
    LocatePre --> InitStart("令 start 等于 pre 的 next")
    InitStart --> LoopCheck{"已执行 right-left 次?"}
    
    LoopCheck -- "否" --> SaveNext("1. 暂存: nxt 等于 curr 的 next")
    SaveNext --> Bridge("2. 跨越: curr 的 next 指向 nxt 的 next")
    Bridge --> Insert("3. 头插: nxt 的 next 指向 pre 的 next")
    Insert --> Reconnect("4. 接头: pre 的 next 指向 nxt")
    Reconnect --> LoopCheck
    
    LoopCheck -- "是" --> Return("返回 Dummy 的 next")

---

五、 复杂度分析与优化建议

• 时间复杂度：$O(n)$。我们只遍历了一次链表（定位到 $left$ 需要 $O(left)$，翻转区间需要 $O(right-left)$）。
• 空间复杂度：$O(1)$。只额外使用了 dummy, pre, curr, nxt 这几个指针变量。

优化建议：

1. 针对 $left=1$：如果不使用 dummy 节点，你需要写大量的 if (left == 1) 判断，这在考场上极易漏掉某种特殊情况。强制养成使用 dummy 的习惯。
2. 减少指针变量引用：在写 pre->next = nxt 这类语句时，务必保证 pre 此时非空。

---

六、 读题关键词总结

在处理这类“区间/部分”操作的题目时，注意这些信号：

1. “$1 \le left$”：当最小值可能是 1 时，一定要考虑原头节点被换掉的可能性。
2. “一趟扫描”：这是效率优化的核心要求，意味着你不能先数总长度，再反转，再拼接，而应该在移动过程中直接修改指针。
3. “反转” + “区间”：这通常意味着需要维护四个指针：区间前、区间内头、区间内尾、区间后。

教练寄语： 同学，Reverse Linked List II 的精髓在于指针的平移。请你在纸上画出 $left=1$ 的情况，看看你的 dummy 节点是如何保护程序不崩溃的。这一招在以后处理更复杂的链表（如大整数运算、LRU 缓存）时非常管用！

labuladong的递归解法