61.反转链表 II
题目
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
其中位置从 1 开始计数。
示例 1：
- 输入：head = [1,2,3,4,5], left = 2, right = 4
- 输出：[1,4,3,2,5]
示例 2：
- 输入：head = [5], left = 1, right = 1
- 输出：[5]
提示：
- 链表中节点数目为 n
- 1 <= n <= 500
- -500 <= Node.val <= 500
- 1 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
思路
头插法(一次遍历，最优雅)
这个方法只走一遍链表，思路是: 把left到right之间的节点，一个一个的摘下来，插到最前面。
- 找到left前面那个节点，我们叫他pre(precursor前驱)。它是这段反转区域的守门人，会一直不动。
dummy → 1 → 2 → 3 → 4 → 5
↑
pre (left=2 时，pre 就是节点 1)
-
定义cur为反转区域的第一个节点(这里是2)。注意: 反转过程中cur始终指向那段的第一个节点(它会不断被往后挤)
-
每次把cur的下一个节点next摘下来，然后插到pre后面，重复right - left次。
动画演示:
pre = 1 cur = 2
dummy -> 1 -> 2 -> 3 -> 4 -> 5
第一次把cur.next也就是3摘下来插到pre后面
pre = 1 cur = 2
dummy -> 1 -> 3 -> 2 -> 4 -> 5
注意，这里cur还是2，只是它被挤到后面了。
第二次把cur.next也就是4摘下来插到pre后面
pre = 1 cur = 2
dummy -> 1 -> 4 -> 3 -> 2 -> 5
这样做了right - left = 4 - 2 = 2次，结束，中间段变成了4 -> 3 -> 2。
每一次摘下来插到前面其实就是三步:
val next = cur.next // 1. 记住要移动的节点
cur.next = next.next // 2. cur 越过 next，接到 next 的后面（把 next 摘出来）
next.next = pre.next // 3. next 插到 pre 后面：先指向 pre 原来的第一个
pre.next = next // 4. pre 指向 next，完成头插
记忆口诀: 摘出next，让它插队到pre后面
class ListNode(var `val`: Int) {
var next: ListNode? = null
}
class Solution {
fun reverseBetween(head: ListNode?, left: Int, right: Int): ListNode? {
// 1. 建立哨兵节点，指向 head，避免 left == 1 时需要特殊处理
val dummy = ListNode(0)
dummy.next = head
// 2. 让 pre 走到 left 的前一个节点（走 left-1 步）
var pre: ListNode = dummy
for (i in 0 until left - 1) {
pre = pre.next!!
}
// 3. cur 是反转区域的第一个节点，反转过程中它始终指向这一段的第一个节点
// （它会被后续节点不断"挤"到后面）
val cur: ListNode = pre.next!!
// 4. 头插法：把 cur 后面的节点依次摘下，插到 pre 的后面
// 一共执行 right - left 次
for (i in 0 until right - left) {
// 要被移动的节点
val next: ListNode = cur.next!!
// cur 越过 next（把 next 摘出来）
cur.next = next.next
// next 插到 pre 后面：先接上原来的第一个
next.next = pre.next
// pre 指向 next，完成插入
pre.next = next
}
// 5. 返回真正的头节点
return dummy.next
}
}
引入"哨兵节点"（dummy）避免特殊情况
有个坑：如果 left = 1，也就是从第一个节点就开始反转，那"前面的节点"就不存在了，代码里要写一堆 if 判断。
解决办法是在真正的头节点前面加一个虚拟节点 dummy，让它指向 head。这样无论 left 是不是 1，前面永远都有一个节点可以操作，代码统一，不用特判。
dummy → 1 → 2 → 3 → 4 → 5
最后返回 dummy.next 就是真正的头。
三个容易踩的坑:
- 忘记用 dummy 节点 —— 当 left = 1 时，pre 前面没有节点，不用 dummy 就得写一堆特判。
- 误以为 cur 要往后移动 —— 头插法里 cur 是不动的（它逻辑上一直是那段的第一个节点，只是物理位置被往后挤），真正移动的是 cur.next。
- 三步操作顺序写错 —— 必须先 val next = cur.next 把节点存起来，否则指针一改就找不到它了。
这道题的核心就是处理好"前后两个接口" + 用 dummy 消除边界特判 + 头插法一次搞定。掌握了这三点，同类的链表反转题都能套用。
复杂度
- 时间复杂度: O(n)：pre 走到位置 left 最多 n 步，反转循环最多 n 步，只遍历一遍链表。
- 空间复杂度: O(1)：只用了几个指针变量，没有额外开辟空间。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!