92. Reverse Linked List II

Leetcode link

题目简介

/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */

这题是 206 的变体，它不再要求我们反转整个链表，而是只反转 [left, right] 区间的链表

解题思路

这道题有一个非常巧妙的思路

我们用 head=[1, 2, 3, 4, 5], left=2, right=4 为例

首先我们需要用一个指针 prev 指向 left 的上一个元素（也就是 1）

接着我们需要把链表中的 2 与 3 进行翻转，翻转后的链表变成：[1, 3, 2, 4, 5]

接下来我们要把链表中的 [3, 2] 以及 4 进行翻转，翻转后的链表变成：[1, 4, 3, 2, 5]

这就是我们的预期结果

所以这题的解题步骤就是：

1. 找到 prev 指针的位置
2. 将 prev 指针后面的元素翻转 right-left 次
3. 最后返回新的链表头

为了处理 left=1 的情况，我们可以用一个 dummy 元素（其 next 指针指向原来的 head）来操作

Javascript

/**
 * 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

    // we should put prev a node ahead the left node
    for (let i = 0; i < left - 1; i++) {
        prev = prev.next
    }

    // head: 1->2->3->4->5, left: 2, right: 4
    // now we put prev at 1
    let cur = prev.next
    for (let j = 0; j < right - left; j++) {
        // first we swap 2 and 3
        // second we swap 32 and 4
        let temp = cur.next
        cur.next = temp.next
        temp.next = prev.next
        prev.next = temp
    }

    return dummy.next
};

复杂度分析

时间

O(n)

空间

O(1)