92.反转链表II
92. 反转链表 II
题意
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位
置 left 到位置 right 的链表节点，返回 反转后的链表 。
难度
中等
示例
示例 1：
092.%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8II-20231018204707.png
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
分析
本题依然是链表相关的题目，比较考验我们对节点位置的把握能力。
这次我们打算采用头插法：
利用一个永远指向翻转区域前的节点，然后再利用一个 cur 变量指向即将要翻转
的元素，再加一个 next 变量指向 cur 的下一个节点。接着不断移动并修改 cur
和 next，将 next 替换成 next 的下一个节点，并且将 cur 替换为 next。
一图胜千言，来看图！
092.%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8II-20231019113106.png
按照图示的方法来进行拆解，大家就能够豁然开朗了。实际上就下面这几个步骤：
• 保持 pre 的位置不变
• 获取 cur 的 next，赋值给 nxt 变量
• 修改 cur 的下一个位置为 nxt 的 next
• 将 pre 的 next 修改为 nxt。
通过不断变换 cur 和 nxt 的相对位置，将 nxt 提到 pre 后面，与此同时 cur 的位置也就自
然而然地向后移动了。
为了避免代码的冗长，我们加入了 dummy 这个 头节点的父亲节点，来看题解。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
*}
*/
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(-1,head);
ListNode pre = dummy;
for (int i = 1;i <= left - 1;i++) {
pre = pre.next;
}
ListNode cur = pre.next;
for (int i = 1;i <= right - left;i++) {
ListNode next = cur.next;
cur.next = next.next;
next.next = pre.next;
pre.next = next;
}
return dummy.next;
}
}
详细分析：
1. 为了处理在反转区间内可能会反转到头节点的情况，我们创建了一个虚拟头节点
dummy。
2. 我们首先找到开始反转的前一个节点 pre。这是为了在后续的反转过程中，我们可以
轻松地在 pre 和 cur 之间插入节点。
3. 我们初始化 cur 为反转区间的第一个节点。
4. 在反转过程中，我们每次都取 cur 的下一个节点 next，然后更新 cur 的 next 指针，
使其跳过 next。
5. 接着，我们把 next 插入到 pre 之后（反转区间的开始）。这样，我们实际上是每次
都把 cur 的下一个节点移动到反转区间的开始位置。
6. 反复进行上述操作，直到整个反转区间都被反转完毕。
这个方法的巧妙之处在于，我们不是单纯地在反转区间内交换节点的位置，而是每次都把
cur 的下一个节点 next 移动到反转区间的开始位置，这样就达到了反转的效果。
当输入是 head = [1,2,3,4,5], left = 2, right = 4 时，我们来模拟一下整个题解过程。
链表初始状态：
1 -> 2 -> 3 -> 4 -> 5
①. 创建一个虚拟头节点 dummy 并使其指向 head。虚拟头节点的用途是简化操作，尤其
是当 left 为 1 时，即需要反转包括头节点在内的子段。
dummy(-1) -> 1 -> 2 -> 3 -> 4 -> 5
②. 初始化 pre 为虚拟头节点并移动它到反转段的前一个位置。这里 left 是 2，所以 pre 将
移动 1 次并指向节点 1。
pre
|
dummy(-1) -> 1 -> 2 -> 3 -> 4 -> 5
1. cur 是反转段的第一个节点，所以它现在指向 2。
2. 开始反转操作，我们的目标是反转 2、3、4 这三个节点。
第一次反转（移动节点 3 到 2 之前）：
next
|
dummy(-1) -> 1 -> 2 -> 3 -> 4 -> 5
pre cur
操作后：
dummy(-1) -> 1 -> 3 -> 2 -> 4 -> 5
pre cur next
第二次反转（移动节点 4 到 3 之前）：
next
|
dummy(-1) -> 1 -> 3 -> 2 -> 4 -> 5
pre cur next
操作后：
dummy(-1) -> 1 -> 4 -> 3 -> 2 -> 5
pre cur next
③. 所有的反转操作都完成了。新链表现在是：
dummy(-1) -> 1 -> 4 -> 3 -> 2 -> 5
④. 返回 dummy.next，即新的头节点。结果为：
1 -> 4 -> 3 -> 2 -> 5
所以，对于输入 head = [1,2,3,4,5], left = 2, right = 4，经过反转操作后的链表为 1 ->
4 -> 3 -> 2 -> 5。
来看一下题解效率。
092.%E5%8F%8D%E8%BD%AC%E9%93%BE%E8%A1%A8II-20231019113927.png
总结
链表类题目，主要考察的是我们对节点位置的把握能力，以及对链表操作的熟练程度。这
道题目的解法非常巧妙，我们可以通过不断地移动 cur 和 nxt 的相对位置，将 nxt 提到
pre 后面，与此同时 cur 的位置也就自然而然地向后移动了。
力扣链接：https://leetcode.cn/problems/reverse-linked-list-ii/
