链表排序为什么常用归并排序？快慢指针如何拆分链表？

简化版

链表排序常用归并排序，因为链表不适合随机访问，但很适合拆分和合并。

用快慢指针找到链表中点，把链表断成两半，递归排序左右链表。

最后用合并两个有序链表的方式合并，时间复杂度 O(n log n)，额外空间主要是递归栈。

详细版

数组排序常用快排，但链表上快排 partition 需要频繁改指针，不如归并自然。

链表归并排序流程：

如果链表为空或只有一个节点，直接返回；
用快慢指针找到中点；
从中点断开链表；
递归排序左右两段；
合并两个有序链表。

合并阶段只需要改 next 指针，不需要额外复制大量元素。

完整版教学

一、为什么链表不适合普通数组排序思路

链表不能通过下标 O(1) 访问中间元素，很多依赖随机访问的排序技巧会变得别扭。比如堆排序需要频繁访问父子下标，快排分区也需要大量交换节点或值。归并排序只需要顺序遍历和改指针，天然贴合链表结构。

记忆钩子：数组怕搬运，链表怕随机访问；链表排序优先想归并。

排序思路	数组适配性	链表适配性
快速排序	随机访问和交换方便	分区改指针较麻烦
堆排序	下标访问父子节点方便	随机访问差
归并排序	需要辅助数组	顺序合并很自然

二、快慢指针如何找中点

快指针一次走 2 步，慢指针一次走 1 步。当快指针到尾部时，慢指针接近中点。为了断链，通常还需要记录慢指针前一个节点 prev。

1 -> 4 -> 2 -> 3
slow 最终到 2 附近
prev.next = null 断成两段

断链非常重要，否则递归时左右链表仍然连在一起，会造成无限递归。

三、分治递归结构

链表排序的分治结构和归并排序一致：

sort(head)
├─ sort(left half)
└─ sort(right half)
merge(left, right)

每次拆成两半，问题规模减半；合并时线性扫描两个已排序链表。递归深度约为 log n。

四、代码模板

实现如下：

function sortList(head) {
  if (!head || !head.next) return head

  let slow = head
  let fast = head
  let prev = null
  while (fast && fast.next) {
    prev = slow
    slow = slow.next
    fast = fast.next.next
  }
  prev.next = null

  const left = sortList(head)
  const right = sortList(slow)
  return merge(left, right)
}

function merge(a, b) {
  const dummy = { next: null }
  let cur = dummy
  while (a && b) {
    if (a.val <= b.val) {
      cur.next = a
      a = a.next
    } else {
      cur.next = b
      b = b.next
    }
    cur = cur.next
  }
  cur.next = a || b
  return dummy.next
}

相等时优先接左链表节点，可以保持稳定性。

五、复杂度分析

每一层合并所有链表段，总共会访问 n 个节点。递归层数是 log n，所以时间复杂度是：

O(n log n)

自顶向下递归需要 O(log n) 调用栈。若用自底向上归并，可以把额外栈空间降到 O(1)，但实现更复杂。

六、常见误区与追问

误区：找到中点后忘记断链。 左右链表仍连接会导致递归无法缩小问题。
误区：合并时创建新节点。 可以直接复用原节点，避免额外内存和数据复制。
误区：认为链表归并一定 O(n) 空间。 辅助数组不需要，递归栈是 O(log n)；自底向上可做到常数额外空间。
追问：为什么不使用快排？ 链表随机访问差，快排分区和交换不如数组自然，且稳定性也不好。
追问：如何处理偶数长度链表中点？ 只要能拆成两个更短链表即可，左右差 1 不影响复杂度。

这些问题考的是链表结构和排序算法的匹配度。

七、加强记忆

链表排序记成“快慢找中点，断链分两半，归并接指针”。分治负责把大链表拆小，合并负责把两个有序链表线性拼回去。链表不擅长随机访问，所以归并比很多数组排序更自然。写代码时最重要的坑是断链和复用节点。

简化版

详细版