力扣链接：92.反转链表 II

难度：⭐⭐
- 推荐方法二

✏️ 方法一：

解题关键词：链表、栈

解题思路：将指定区间内的元素入栈，之后逐个出栈。

function reverseBetween(
  head: ListNode | null,
  left: number,
  right: number
): ListNode | null {
  let count = 1;
  const stack = [];

  const preHead = new ListNode(-1, head);
  let slow = preHead;
  let fast = head;

  // 将两个指针一直往前移动
  while (count < left && fast) {
    count++;
    slow = slow.next;
    fast = fast.next;
  }

  // 此时肯定等于 left，如果不等于说明 left 大于了数组的长度
  if (count !== left) {
    return head;
  }

  // 入栈
  while (count <= right && fast) {
    stack.push(fast);
    fast = fast.next;
    count++;
  }

  // 出栈
  while (stack.length) {
    const target = stack.pop();
    slow.next = target;
    slow = slow.next;
  }

  slow.next = fast;

  return preHead.next;
}

✏️ 方法二：

解题关键词：链表

解题思路：遍历到区间中的元素，我们总是把后面的元素插到区间的最前面。

function reverseBetween(
  head: ListNode | null,
  left: number,
  right: number
): ListNode | null {
  const preHead = new ListNode(-1, head);

  let pre = preHead;

  // 将指针移动到区间起点左边的节点
  for (let i = 0; i < left - 1; i++) {
    pre = pre.next;
  }

  let cur = pre.next;

  // 不断插入到最前面
  for (let i = 0; i < right - left; i++) {
    const next = cur.next;
    cur.next = next.next;
    next.next = pre.next;
    pre.next = next;
  }

  return preHead.next;
}