如何对单链表进行排序？为什么首选归并排序？

简化版

链表排序首选归并排序：用快慢指针找中点把链表断成两半，递归排好左右两段，再合并两个有序链表。归并对链表特别友好——合并只需改指针不用搬移数据，分割也只需找中点，能做到 O(n log n) 时间。相比之下快排在链表上不好用（不能随机访问、难取中位数）。

详细版

链表不能像数组那样随机访问 a[mid]，所以依赖随机访问的排序（快排取基准、堆排序建堆）在链表上都别扭。归并排序只需要「顺序访问 + 拆分 + 合并」，正好都是链表擅长的：

ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    // 1. 快慢指针找中点并断开
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next; fast = fast.next.next;
    }
    ListNode mid = slow.next;
    slow.next = null;                 // 断成两段
    // 2. 递归排序左右
    ListNode left = sortList(head), right = sortList(mid);
    // 3. 合并两个有序链表
    return merge(left, right);
}
ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    return dummy.next;
}

时间 O(n log n)，空间 O(log n)（递归栈）。
用「自底向上」的迭代归并可把空间降到 O(1)。

完整版教学

一、为什么不用快排/堆排序

快速排序：核心是「选基准 + 分区」，分区时需要频繁访问两端元素、交换，链表没有随机访问、也不能从尾往前走，实现别扭且难保证平衡（取中位数难），最坏 O(n²)。
堆排序：需要按下标访问建堆（2i+1、2i+2），链表做不到 O(1) 定位。
归并排序：只需要「找中点拆分」和「合并有序链表」，两者都只涉及顺序遍历和改指针，完美契合链表。所以链表排序几乎都用归并。

二、归并三步：分、治、并

分（split）：快慢指针找中点，把链表从中间断成两条独立的子链（slow.next = null 是关键，忘了断会死循环）。
治（sort）：对左右两段递归调用排序，直到子链只剩 0 或 1 个节点（天然有序）。
并（merge）：合并两个有序链表——用哑节点 dummy 起头，每次挑两条链表头里较小的接到结果尾部。这一步 O(n)，且只改指针、不移动数据，正是链表的强项。

三、链表归并 vs 数组归并的差异

数组归并的「合并」需要一个额外的临时数组来存合并结果（O(n) 辅助空间）。而链表归并的合并不需要额外数组——直接把节点用指针串起来即可，省掉了那份 O(n) 辅助空间。这是链表相对数组做归并的一个隐藏优势。

四、递归 vs 自底向上迭代

自顶向下递归（上面的写法）：好理解，但递归深度 O(log n)，有栈空间开销。
自底向上迭代：从长度 1 的子链开始，两两合并成长度 2、4、8…的有序段，逐轮扩大。不用递归，空间 O(1)。是「常数空间排序链表」的标准答案，代码稍复杂但空间最优。

五、易错点

找中点后一定要断开（slow.next = null），否则两段还连着，递归无法终止。
快慢指针初始化 fast = head.next 能让偶数长度时 slow 停在前半段末尾，保证两段尽量均分、也避免长度为 2 时死循环。
合并用哑节点简化头部处理。

六、常见误区与追问

排序算法	链表上是否推荐	原因
归并排序	推荐	顺序访问、拆分、合并都适合链表
快速排序	不优先	难随机取基准，分区和交换不方便
堆排序	不推荐	堆依赖数组下标随机访问
插入排序	小数据可用	最坏 O(n²)，适合近乎有序短链表

易错点：链表归并排序的“断开”不是可选步骤。slow.next = null 漏掉后，递归子问题仍然连着原链表，很容易无限递归。

用 8 个节点看复杂度：第一层拆成两个 4，第二层拆成四个 2，第三层拆成八个 1，一共约 log2(8)=3 层；每一层合并时所有节点总共被扫描一次，所以总工作量约 8 * 3，推广为 O(n log n)。链表合并只改 next，不需要像数组那样搬移一段连续元素。

误区：数组上快排常用，所以链表排序也首选快排。 链表缺少随机访问和从尾向前扫描能力，快排分区实现成本高且不稳定。
误区：归并链表一定需要 O(n) 额外数组。 链表合并可以原地改指针，递归版主要额外空间是调用栈。
误区：找中点时 fast 怎么初始化都不影响。 fast=head.next 常用于让 slow 停在前半段末尾，便于断链并避免长度为 2 时递归不收敛。
追问：如何做到 O(1) 额外空间？ 使用自底向上迭代归并，按子链长度 1、2、4、8 逐轮合并，避免递归栈。
追问：归并排序稳定吗？ 合并时相等元素优先接左链表，可以保持稳定性。
追问：为什么链表合并比数组合并更适配？ 链表节点可通过指针重连成结果，不需要额外数组承载合并后的序列。

七、加强记忆

链表排序首选归并：快慢指针找中点断成两半 → 递归排序 → 合并两个有序链表（只改指针、不搬数据，还省掉数组归并的辅助空间）。O(n log n) 时间，递归 O(log n) 空间、自底向上迭代可降到 O(1)。快排/堆排序依赖随机访问，在链表上不好用。别忘了拆分时 slow.next=null 断开。

简化版

详细版