0092.反转链表 II
难度：🟡 中等
标签：链表
链接：92. 反转链表 II
题目描述
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，并返回 反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
解题思路
核心思想
本题的目标是在原地反转链表的一个指定区间 [left, right]。这需要我们精确定位到区间的边界，对区间内的节点进行反转，然后将反转后的子链表正确地接回原链表中。
思路选择
迭代法 + 虚拟头节点（Dummy Head） 是解决此问题的标准最优思路。
虚拟头节点：创建一个
dummy节点，其next指向原始的head。这可以极大地简化边界情况的处理，尤其是当反转区间包含头节点时（即left = 1）。定位前驱节点：我们首先需要找到待反转区间的前一个节点，我们称之为
prev。这个节点位于left - 1的位置。头插法反转：从
left位置的节点开始，我们依次将后面的节点通过“头插法”的方式，移动到prev节点的后面。具体来说，就是将left后面的节点，逐个地、依次地插入到prev和prev.next之间。
关键步骤
创建虚拟头节点：
let dummy = new ListNode(0, head)，并让一个指针prev指向它。定位前驱节点：将
prev指针向前移动left - 1步，使其到达待反转区间的前一个节点。初始化当前节点：用一个
current指针指向待反转区间的第一个节点，即prev.next。循环反转：循环
right - left次。在每次循环中： a. 定义一个nextNode指向current.next，这是将要被移动到前面的节点。 b.current跳过nextNode，直接指向nextNode.next。 c. 将nextNode插入到prev之后，即nextNode.next = prev.next，然后prev.next = nextNode。返回结果：所有操作完成后，返回
dummy.next，它指向新链表的头节点。
代码实现
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} left
* @param {number} right
* @return {ListNode}
*/
var reverseBetween = function(head, left, right) {
if (!head || left === right) return head;
const dummy = new ListNode(0, head);
let prev = dummy; // prev 指向待反转区间的前一个节点
// 1. 移动 prev 到 left - 1 的位置
for (let i = 0; i < left - 1; i++) {
prev = prev.next;
}
// current 指向待反转区间的第一个节点
let current = prev.next;
// 2. 循环 right - left 次，使用头插法反转
for (let i = 0; i < right - left; i++) {
const nextNode = current.next;
current.next = nextNode.next;
nextNode.next = prev.next;
prev.next = nextNode;
}
return dummy.next;
};
复杂度分析
时间复杂度：O(n) 其中 n 是链表的长度。我们最多只需要对链表进行一次完整的遍历。
空间复杂度：O(1) 我们只使用了常数个额外变量作为指针，操作是在原链表上进行的，空间消耗是恒定的。
相关题目
总结
本题是链表原地操作的进阶题目，是面试中的高频题。其迭代解法中的“头插法”非常精妙，它通过在固定前驱节点后不断插入后续节点，实现了区间的原地反转。虚拟头节点的运用同样至关重要，它统一了所有情况的处理逻辑，使代码更加健壮和简洁。