【数据结构与算法】力扣 92. 反转链表 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]

提示：

• 链表中节点数目为 n
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

分析解答

这道题和反转链表的唯一不同是它存在起始和结束位置，所以我们只需要在原有反转链表的基础上，再思考一下如何将反转后的小链表和之前的链表连接起来，也就是需要多思考两个指针（next）的指向。

代码如下：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
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;
    let dummy = new ListNode(0); // 创建虚拟头节点
    dummy.next = head;
    let prev = dummy;
    for (let i = 0; i < left - 1; i++) {
        prev = prev.next;
    }
    let current = prev.next;
    for (let i = 0; i < right - left; i++) {
        let next = current.next;
        current.next = next.next;
        next.next = prev.next;
        prev.next = next;
    }
    return dummy.next;
};

重点在于：

let next = current.next;
current.next = next.next;
next.next = prev.next;
prev.next = next;

对比普通反转列表代码：

let temp = cur.next; 
cur.next = pre; 
pre = cur; 
cur = temp;

普通反转链表（全部反转）：

1. 缓存下一个值
2. 改变 cur 的 next 指向（指向上一个）
3. pre 移动到 cur 的位置
4. cur 移动到下一个位置（缓存值）

部分反转：

1. 缓存下一个值
2. 改变 cur 的 next 指向（指向下一个的下一个）
3. 改变下一个值的 next 指向
4. 改变上一个值的 next 指向

除此之外，如果需要反转三个数据。部分反转循环代码块执行两次（反转两次）；而全部反转循环代码块执行三次（反转三次，有一次 null 头节点）。

这样看来，只是三四代码语句有区别，而这两句代码正好对应了我上面说到的那两次不同的指针改变。

思路拓展