排序链表

更新: 7/5/2026 字数: 0 字 时长: 0 分钟

LeetCode 148. Sort List

题目描述

给你链表的头结点 head，请将其按 升序 排列并返回排序后的链表。

进阶要求：你可以在 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

输入：head = []
输出：[]

思路拆解：从暴力到最优

想法一：倒进数组排序（暴力解法）

链表不方便随机访问，那就把所有值倒进数组，用语言自带的排序排好，再把值写回链表。

点击展开暴力解法

function sortList(head) {
  const arr = [];
  let p = head;
  while (p) {           // 1) 把值全部倒进数组
    arr.push(p.val);
    p = p.next;
  }
  arr.sort((a, b) => a - b); // 2) 数组排序 O(n log n)
  p = head;
  let i = 0;
  while (p) {           // 3) 把排好的值写回链表
    p.val = arr[i++];
    p = p.next;
  }
  return head;
}

• 时间：，排序主导。
• 空间：，额外开了一个数组。

它能过，但没满足进阶的常数级空间要求——因为借用了数组。

为什么暴力不够好？

数组解法把「排序」和「链表」割裂开了：先脱离链表结构排序，再灌回去。它没有利用链表指针可以 O(1) 断开与拼接的特性，也就浪费了这个结构本身的优势。要做到 级额外空间，就得让排序直接在指针上进行。

想法二：归并排序（最优解法）

排序算法里，哪一种天生适合链表？答案是 归并排序（Merge Sort）。

原因很直接：

• 归并排序的核心是「分」和「合」。
• 「分」——链表找中点、把一条链切成两条，只需要改一个 next 指针；
• 「合」——合并两条有序链表，是链表的经典操作（LeetCode 21），只需挪指针，不需搬数据。

而快速排序依赖随机访问定位基准，在链表上并不友好。所以链表排序 = 归并排序几乎是标准答案。

核心思路

分（divide）→ 治（sort）→ 合（merge） 三步走：

1. 找中点断链：用快慢指针找到链表中间，从中间断成左右两条独立的链表。
2. 递归排序：分别对左半、右半递归排序（一直拆到只剩单个节点，单节点天然有序）。
3. 合并有序链：把两条排好序的子链表合并成一条有序链表，逐层向上返回。

关键操作 1：快慢指针找中点并断链

slow 一次走一步，fast 一次走两步。当 fast 到末尾时，slow 恰好在中间。

这里有个断链的细节：我们需要在 slow 之前断开，所以额外用一个 prev 记录 slow 的前驱，最后 prev.next = null，把链表一分为二。

关键操作 2：合并两条有序链表

用一个**哑结点（dummy）**当结果链表的头，tail 指针每次挑两条链表中更小的那个接上去，像拉拉链一样把两条链合成一条。

动态演示

下面的动画完整演示了对 [4,2,1,3] 进行归并排序的分治与合并全过程，可以逐步观看链表如何被拆开、又如何合并回有序链表：

步骤 1 / 7分：拆分链表

未处理拆分中合并中已有序

4→

2→

1→

3

初始链表，准备用快慢指针从中点切开。

完整代码（JavaScript）

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function sortList(head) {
  // 递归出口：空链表或只剩一个节点，天然有序
  if (!head || !head.next) return head;

  // 1) 快慢指针找中点，prev 记录 slow 前驱以便断链
  let slow = head, fast = head, prev = null;
  while (fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
  prev.next = null;        // 从中间断开：左半 [head..prev]，右半 [slow..]
  const mid = slow;

  // 2) 递归排序左右两半
  const left = sortList(head);
  const right = sortList(mid);

  // 3) 合并两条有序链表
  return merge(left, right);
}

/** 合并两条有序链表（LeetCode 21） */
function merge(l1, l2) {
  const dummy = new ListNode(-1);
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) {   // 挑更小的接上，注意 <= 保证稳定性
      tail.next = l1;
      l1 = l1.next;
    } else {
      tail.next = l2;
      l2 = l2.next;
    }
    tail = tail.next;
  }
  tail.next = l1 || l2;       // 接上剩余部分
  return dummy.next;
}

进阶：自底向上归并（真正的 O(1) 空间）

上面的递归写法虽然优雅，但递归栈会占用 空间。若要严格做到 空间，可以用自底向上的迭代归并：先按步长 1 两两合并，再步长 2、4、8……直到步长 ≥ 链表长度。

function sortList(head) {
  if (!head || !head.next) return head;
  // 统计链表长度
  let n = 0;
  for (let p = head; p; p = p.next) n++;

  const dummy = new ListNode(-1);
  dummy.next = head;

  for (let size = 1; size < n; size <<= 1) {
    let prev = dummy, cur = dummy.next;
    while (cur) {
      const left = cur;                 // 第一段，长 size
      const right = split(left, size);  // 第二段，长 size
      cur = split(right, size);         // 剩余部分
      prev = mergeTail(prev, left, right); // 合并并把 prev 挪到合并段尾
    }
  }
  return dummy.next;
}

/** 从 head 起切下 size 个节点，返回剩余部分的头，并断链 */
function split(head, size) {
  for (let i = 1; head && i < size; i++) head = head.next;
  if (!head) return null;
  const next = head.next;
  head.next = null;
  return next;
}

/** 把 l1、l2 合并接到 prev 之后，返回合并段的尾结点 */
function mergeTail(prev, l1, l2) {
  let tail = prev;
  while (l1 && l2) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
    else { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 || l2;
  while (tail.next) tail = tail.next; // 走到合并段尾
  return tail;
}

它把递归改成了循环，不再有递归栈，空间降到 （不计输出）。

复杂度分析

设链表长度为 。

解法	时间复杂度	空间复杂度	说明
倒进数组排序			借助额外数组，不满足进阶
递归归并排序			递归栈深度为 ，最常写
自底向上归并			迭代，真正常数空间

为什么是 ？ 归并排序共有 层，每一层的合并操作会遍历全部 个节点，所以总时间是 。这也是基于比较的排序能达到的理论最优下界。

边界与易错点

易错点

1. 断链一定要断干净。找到中点后必须执行 prev.next = null，否则左半链表的尾还连着右半，递归会死循环或结果错乱。只用 slow 而不记 prev 是新手最常见的坑。

2. 快慢指针的起点。本题让 fast = head（而不是 head.next）。对偶数长度链表，slow 会停在右半的第一个节点，配合 prev 断链后左右两半长度平衡，能保证递归收敛。

3. 递归出口。if (!head || !head.next) return head; 必须同时判空链表和单节点，缺一个都会在拆到底时出错。

4. 合并时用 <= 而非 <。相等时优先接 l1，能保证排序的稳定性（相等元素相对顺序不变）。

5. 别忘接尾巴。merge 结束后一定要 tail.next = l1 || l2，把较长链表的剩余部分接上，否则会丢节点。

6. 空链表 / 单节点。head 为 null 或只有一个节点时应直接返回，递归出口已覆盖。

简易解题思路（记忆口诀）

「快慢找中点，一刀切两半；左右各排好，拉链合一线。」

拆开记：

口诀	对应操作
快慢找中点	slow 走一步、fast 走两步，快到头时慢在中间
一刀切两半	用 prev.next = null 从中点前断链，分成左右两条
左右各排好	递归 sortList(left)、sortList(right)，拆到单节点为止
拉链合一线	用 dummy 哑结点，每次挑小的接上，两条有序链合成一条

一句话记住本质：链表排序就是归并排序——「先拆到不能再拆，再一层层拉链拼回去」。