92. 反转链表 II

[webVueBlog]

给你单链表的头指针 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
 

/**
 * 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}
 92. 反转链表 II
left = 2 right = 4
定义一个虚拟的头节点

 -1 -> 1 -> 2 -> 3 -> 4 -> 5
 pre  cur
      pre  cur
      pre            cur

            2 -> 3 -> 4
            p    q
 */
var reverseBetween = function(head, left, right) {
    const newNode = new ListNode(-1, head)
    let pre = newNode, cur = head, next
    let n = right - left + 1
    while(--left) {
        pre = pre.next
        cur = cur.next
    }
    while(--n) {
        cur = cur.next
    }
    next = cur.next
    cur.next = null
    const reverseHead = reverse(pre.next, next)
    pre.next = reverseHead
    return newNode.next
};

var reverse = function (head, next) {
    let pre = head, cur = head.next
    while(head.next) {
        head.next = cur.next
        cur.next = pre
        pre = cur
        cur = head.next
    }
    head.next = next
    return pre
}

[webVueBlog]

/**
 * 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}
 92. 反转链表 II
left = 2 right = 4
定义一个虚拟的头节点
 */
var reverseBetween = function(head, left, right) {
    const newNode = new ListNode(-1, head)
    let pre = newNode, cur = head
    let n = right - left + 1
    while(--left) {
        pre = pre.next
        cur = cur.next
    }
    while(--n) {
        const q = cur.next
        cur.next = q.next
        q.next = pre.next
        pre.next = q
    }
    return newNode.next
};

[webVueBlog]

var reverseBetween = function(head, left, right) {
    const dummyNode = new ListNode(-1);
    dummyNode.next = head; // 虚拟头节点

    let pre = dummyNode;
    for (let i = 0; i < left - 1; i++) { // pre遍历到left的前一个节点
        pre = pre.next;
    }

    let rightNode = pre;
    for (let i = 0; i < right - left + 1; i++) { // rightNode遍历到right的位置
        rightNode = rightNode.next;
    }

    let leftNode = pre.next; // 保存leftNode
    let curr = rightNode.next; // 保存rightNode.next

    // 切断left到right的子链
    pre.next = null;
    rightNode.next = null;

    // 反转left到right的子链
    reverseLinkedList(leftNode);

    // 返乡连接
    pre.next = rightNode;
    leftNode.next = curr;
    return dummyNode.next;
};

const reverseLinkedList = (head) => {
    let pre = null;
    let cur = head;

    while (cur) {
        const next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
}