反转链表

如何迭代反转整条链表？

• 三指针: pre 保存已反转部分的头, cur 指向待处理结点, next 暂存 cur.next;
• 每轮: 先存后继, 再断链逆转, 最后整体前移;
• 终止: cur === null 时 pre 即新头;

const reverseList = (head) => {
  let pre = null;
  let cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
  }
  return pre;
};

• 时间 $O(n)$, 空间 $O(1)$;

如何递归反转整条链表？

• 假设: head.next 之后的整段已被递归反转并返回新头;
• 收尾: 把 head.next.next 指回 head, 并断开 head.next;
• 终止: 空表或单结点直接返回自身;

const reverseList = (head) => {
  if (!head || !head.next) return head;
  const res = reverseList(head.next);
  head.next.next = head;
  head.next = null;
  return res;
};

• 时间 $O(n)$, 空间 $O(n)$ 递归栈;

如何反转区间 [left, right]？

• 步骤: 哨兵定位到 left 的前驱 start → 从 left 起按迭代法反转 right - left + 1 个结点 → 把反转段的前后接回原链;
• 接回: start.next 指向反转后的段头 (pre), 反转段原来的首结点 (start.next 的旧值) 的 next 指向 cur;

const reverseBetween = (head, left, right) => {
  const dummy = new ListNode(-1, head);
  let pre = null;
  let cur = dummy;
  let index = 0;
  while (index < left) {
    pre = cur;
    cur = cur.next;
    index++;
  }
  const start = pre;
  while (index <= right && cur) {
    const next = cur.next;
    cur.next = pre;
    pre = cur;
    cur = next;
    index++;
  }
  start.next.next = cur;
  start.next = pre;
  return dummy.next;
};

如何每 k 个结点一组反转？

• 复用迭代反转函数;
• 外层循环: 每轮先试探性前进 k 步, 不足 k 步就结束;
• 反转: 记录本段 start 与段后 next, 断开段尾后反转本段, 再把 start.next 接回;
• 时间 $O(n)$, 空间 $O(1)$;

const reverseKGroup = (head, k) => {
  const reverse = (node) => {
    let pre = null;
    let cur = node;
    while (cur) {
      const next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
    return pre;
  };

  const dummy = new ListNode(-1, head);
  let cur = dummy;
  while (cur) {
    const pre = cur;
    for (let i = 0; i < k; i++) {
      cur = cur.next;
      if (!cur) return dummy.next;
    }
    const start = pre.next;
    const next = cur.next;
    cur.next = null;
    pre.next = reverse(start);
    start.next = next;
    cur = start;
  }
  return dummy.next;
};