链表排序

为什么希尔排序和堆排序不适合链表？

• 希尔排序: 需要按下标做 i + gap 的跳跃访问, 链表只能顺序走;
• 堆排序: 堆是一棵完全二叉树, 靠数组下标确定父子关系, 链表定位父/子结点代价高;
• 通用原因: 二者都依赖随机访问, 见 链表结构与变体;

链表插入排序怎么写？

• 维护: dummy 指向整表, sort 指向已排序部分的尾结点, cur 指向待插入结点;
• 快速路径: cur.val >= sort.val 时直接后移 sort;
• 慢速路径: 从 dummy 起找第一个值不小于 cur 的前驱 pre, 把 cur 摘下插到 pre 之后;
• 时间 $O(n^2)$, 空间 $O(1)$;

const insertionSortList = (head) => {
  const dummy = new ListNode(-1, head);
  let sort = head;
  let cur = head.next;
  while (cur) {
    if (cur.val >= sort.val) {
      sort = sort.next;
    } else {
      let pre = dummy;
      while (pre.next.val < cur.val) pre = pre.next;
      sort.next = cur.next;
      cur.next = pre.next;
      pre.next = cur;
    }
    cur = sort.next;
  }
  return dummy.next;
};

链表归并排序怎么写？

• 分: 快慢指针找中点, 用 pre.next = null 断开成两段, 见 链表中双指针;
• 治: 递归排序两段;
• 合: 用哨兵按值串接两条有序链, 见 两个链表的遍历;
• 时间 $O(n \log n)$, 空间 $O(\log n)$ 递归栈;

const sortList = (head) => {
  const merge = (left, right) => {
    const dummy = new ListNode(0);
    let cur = dummy;
    while (left && right) {
      if (left.val < right.val) {
        cur.next = left;
        left = left.next;
      } else {
        cur.next = right;
        right = right.next;
      }
      cur = cur.next;
    }
    cur.next = left ?? right;
    return dummy.next;
  };

  const mergeSort = (node) => {
    if (!node || !node.next) return node;
    let slow = node;
    let fast = node;
    let pre = null;
    while (fast && fast.next) {
      pre = slow;
      slow = slow.next;
      fast = fast.next.next;
    }
    pre.next = null;
    return merge(mergeSort(node), mergeSort(slow));
  };

  return mergeSort(head);
};