35.reverse-linked-list-ii.md

92.反转链表 II

https://leetcode-cn.com/problems/reverse-linked-list-ii/

• 92.反转链表 II
  • 题目描述
  • 方法 1: 两趟扫描
    • 思路
    • 代码
  • 方法 2: 一趟扫描
    • 思路
    • 代码

题目描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法 1: 两趟扫描

思路

比较直白的思路：

• 第一趟扫描先找到需要反转的链表片段的头尾，
• 然后再扫描一遍将这个片段进行反转，
• 最后将反转后的片段和原链表的头尾两段拼接起来就好。

思路很简单，就是各种指针有点绕，具体看代码吧。

代码

JavaScript Code

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function (head, m, n) {
    if (!head || !head.next) return head;

    let startPrev = null, // 第 m-1 个节点
        start = null, // 第 m 个节点
        end = null, // 第 n 个节点
        endNext = null, // 第 n+1 个节点
        cur = head;

    // 第一趟扫描
    // 分别找到上述节点
    let i = 1;
    while (cur && i <= n) {
        if (i < m) {
            startPrev = cur;
        }
        if (i === m) {
            start = cur;
        }
        if (i === n) {
            end = cur;
            endNext = cur.next;
        }
        cur = cur.next;
        i++;
    }

    // 将 m -> n 这段链表进行反转
    // reverseList 可以用循环实现，具体看 206 题
    end.next = null;
    end = reverseList(start);

    // 如果反转不是从第一个节点开始的话
    // 将反转后的片段和原链表左边的那段拼接起来
    if (startPrev) {
        startPrev.next = end;
    }
    // 如果反转是从第一个节点开始的话
    // 把 head 指针指向反转后片段的第一个节点
    else {
        head = end;
    }
    // 将反转后的片段和原链表右边的那段拼接起来
    start.next = endNext;
    return head;
};

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    if (!head || !head.next) return head;
    const lastNode = head.next;
    const newHead = reverseList(head.next);
    lastNode.next = head;
    head.next = null;
    return newHead;
};

方法 2: 一趟扫描

思路

从第 m 个节点开始，不断地把这个节点的 next 拿出来，插到第 m-1 个节点后面，直到第 n-1 个节点，结束操作。

思路很简单，就是链表的删除和插入操作，画个图就比较好理解了。

tips: 用一个 dummy 节点来简化操作，这样就不用分开考虑 m 等于 1 和不等于 1 的情况了。

代码

JavaScript Code

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function (head, m, n) {
    if (!head || !head.next) return head;

    const dummy = new ListNode(null);
    dummy.next = head;

    let prev = dummy,
        cur = prev.next;

    let i = 0;
    while (i < n - 1) {
        i++;

        // prev 是反转片段前的一个节点
        if (i === m - 1) {
            prev = cur;
        }
        if (i < m) {
            cur = cur.next;
        }

        // 在 [m, n) 这段区间里
        // 把 cur 的下一个节点从链表中删掉
        // 再插入到 prev 后面去
        if (i >= m) {
            temp = cur.next;
            cur.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
    }
    return dummy.next;
};