92. 反转链表 II

题目

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

题解

根据 206 反转链表

/**
 * 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) {
  let count = right - left;
  if (!count) return head;
  let i = 1;
  let prev = head; // 子链表的左边起点
  let prevSubHead = head; // 需要反转的子链表的左边起点之前的节点
  let cur = null;
  while (i < left) {
    prevSubHead = prev;
    prev = prev.next;
    i++;
  }
  cur = prev.next;
  let subtail = prev; // 子链表的左边起点反转结束就是子链表的结尾

  // 反转子链表
  while (count) {
    let next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
    count--;
  }

  // 结果
  // prev 子链表头节点
  // cur 子链表尾节点的下一个节点

  // 反转结束后
  // 开始的左边起点之前的节点就指向反转完成的结尾节点
  // 子链表的结尾指向当前节点
  prevSubHead.next = prev;
  subtail.next = cur;
  // left=1 的时候头节点也和子链表的头节点一致
  return left === 1 ? prev : head;
};