链表旋转与重排

如何把链表向右旋转 k 个位置？

• 思路: 先把尾结点接回头结点成环, 再在断点处剪开;
• 断点: 旋转 k 后新的头是原链的倒数第 $k \bmod n$ 个结点, 其前驱即新的尾;
• 定位: 从 head 走 $n - k \bmod n$ 步到达新头, pre 记录其前驱;
• 时间 $O(n)$, 空间 $O(1)$;

const rotateRight = (head, k) => {
  if (!head) return head;
  let cur = head;
  let count = 1;
  while (cur.next) {
    count++;
    cur = cur.next;
  }
  cur.next = head;

  k %= count;
  let n = count - k;
  let pre = null;
  cur = head;
  while (n !== 0) {
    n--;
    pre = cur;
    cur = cur.next;
  }
  pre.next = null;
  return cur;
};

如何重排链表为 "首尾交替" 形式？

• 目标 (143): $L_0 \to L_n \to L_1 \to L_{n-1} \to \dots$;
• 链表版做法: 找中点 → 反转后半 → 交替合并两半 (见 链表中双指针、反转链表);
• 数组版做法: 把结点按顺序放进数组, 用 left、right 双指针重建 next;
• 数组版代价: 空间 $O(n)$, 但重排顺序一目了然;
• 收尾: 最后一轮可能把原结点重复挂上, 必须 cur.next = null 断链;

const reorderList = (head) => {
  const arr = [];
  for (let cur = head; cur; cur = cur.next) arr.push(cur);

  let cur = head;
  let left = 1;
  let right = arr.length - 1;
  while (left <= right) {
    cur.next = arr[right];
    cur = cur.next;
    cur.next = arr[left];
    cur = cur.next;
    right--;
    left++;
  }
  cur.next = null;
  return head;
};