链表分组

链表中"分组"的通用做法是什么？

• 思路: 用两个尾指针分别维护两组结点, 遍历一次把结点挂到对应组尾;
• 收尾: 断开多余引用, 再把第二组的头接到第一组尾;
• 复杂度: 时间 $O(n)$, 空间 $O(1)$;

如何按位置把奇偶结点分开？

• 目标 (328): 所有奇数位结点在前, 偶数位结点在后, 保持各自相对次序;
• 做法: odd、even 两个尾指针交替接结点, evenHead 记住第二组头;
• 收尾: odd.next = evenHead, 并把 even.next 置 null 断环;

const oddEvenList = (head) => {
  if (!head || !head.next || !head.next.next) return head;
  const evenHead = head.next;
  let odd = head;
  let even = evenHead;
  let cur = evenHead.next;
  let isOdd = true;
  while (cur) {
    if (isOdd) {
      odd.next = cur;
      odd = cur;
    } else {
      even.next = cur;
      even = cur;
    }
    isOdd = !isOdd;
    cur = cur.next;
  }
  odd.next = evenHead;
  even.next = null;
  return head;
};

如何按值把结点分到 x 的两侧？

• 目标 (86): 小于 x 的结点在前, 大于等于 x 的在后, 组内保持原相对次序;
• 做法: 两个哨兵 small、big 各带一个尾指针, 遍历时按值挂到对应组;
• 收尾: curBig.next = null 断开原链残留, curSmall.next = big.next 拼接;

const partition = (head, x) => {
  const small = new ListNode(0);
  const big = new ListNode(0);
  let curSmall = small;
  let curBig = big;
  for (let cur = head; cur; cur = cur.next) {
    if (cur.val >= x) {
      curBig.next = cur;
      curBig = cur;
    } else {
      curSmall.next = cur;
      curSmall = cur;
    }
  }
  curBig.next = null;
  curSmall.next = big.next;
  return small.next;
};