#92.反转链表2

var reverseBetween = function (head, left, right) {
  if (head === null) return head;

  const dummy = new ListNode(0, head);

  let leftNode = dummy;
  for (let i = 0; i < left - 1; i++) {
    leftNode = leftNode.next;
  }
  let rightNode = dummy;
  for (let j = 0; j < right; j++) {
    rightNode = rightNode.next;
  }

  let prev = rightNode.next;
  let cur = leftNode.next;
  for (let k = 0; k < right - left + 1; k++) {
    let temp = cur.next;
    cur.next = prev;
    prev = cur;
    cur = temp;
  }

  leftNode.next = prev;

  return dummy.next;
};

var reverseBetween = function (head, left, right) {
  if (head === null) return head;

  const dummy = new ListNode(0, head);

  // 1. 找到 left 前一个节点
  let beforeLeft = dummy;

  for (let i = 1; i < left; i++) {
    beforeLeft = beforeLeft.next;
  }

  // 2. 开始反转 [left, right]
  const leftNode = beforeLeft.next;
  let prev = null;
  let cur = leftNode;

  for (let i = 0; i < right - left + 1; i++) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }

  // 3. 接回链表
  beforeLeft.next = prev;
  leftNode.next = cur;

  return dummy.next;
};