92. Reverse Linked List II

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

Question

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

思路

这题的名字看去上和206题是一个系列的，的确也是翻转链表相关的。但其实和25题更加的相似，特别是都需要reverse(head, tail)这个关键的函数，和dummy head。

/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function (head, left, right) {
    const reverse = (head, tail) => {
        let prev = null;
        let crr = head;
        while (crr) {
            const next = crr.next;
            crr.next = prev;
            if (crr === tail) break;
            prev = crr;
            crr = next;
        }
    };
    const dummy = new ListNode(0, head);
    let localHead, localTail, localHeadLast;
    let position = 0;
    let crr = dummy;
    while (!localHead || !localTail || !localHeadLast) {
        if (position === left - 1) localHeadLast = crr;
        if (position === left) localHead = crr;
        if (position === right) localTail = crr;
        position += 1;
        crr = crr.next;
    }
    const next = localTail.next;
    reverse(localHead, localTail);
    localHeadLast.next = localTail;
    localHead.next = next;
    return dummy.next;
};

End

有些题目的套路比较相似，掌握核心的几个方法。