复盘 · LC 148 排序链表

题目

• 题号：LeetCode 148
• 名称：排序链表（Sort List）
• 难度：Medium
• 链接：leetcode.cn/problems/sort-list
• 今日代码：148-排序链表/index.js

题意

给定单链表头，按结点值升序排序后返回新头。

• 进阶常要求：时间 O(n log n)，空间尽量 O(1)（递归栈除外）→ 链表归并。
• 结点个数可为 0 / 1。

边界：空链、单结点、已有序、逆序、含重复值。

涉及算法

标签	一句话
数组抽出再排	结点放进数组 sort，再按序重接 next（空间 O(n)）
归并排序	快慢找中点拆两半，递归排序后合并有序链（面试标准）

教程对照：13 · 链表进阶 练习清单含本题（归并：找中点拆开再合并）；合并子过程同 21. 合并两个有序链表。

评价我的解法

我的代码（摘自 148-排序链表/index.js，不含本地测例）：

var sortList = function (head) {
  if (!head) {
    return null;
  }
  if (!head.next) {
    return head;
  }
  const nodeArr = [];
  let cur = head,
    next = null;
  while (cur) {
    if (cur.next) {
      next = cur.next;
    } else {
      next = null;
    }
    nodeArr.push(cur);
    cur = next;
  }
  nodeArr.sort((a, b) => {
    return a.val - b.val;
  });
  let pre = null;
  nodeArr.forEach((item) => {
    item.next = null;
    if (!pre) {
      pre = item;
      return;
    }
    pre.next = item;
    pre = item;
  });
  return nodeArr[0];
};

能 AC（30/30），耗时也不差——题目没强卡 O(1) 额外空间时，这条路合法。

• 时间 O(n log n)，空间 O(n)（数组）。
• 对在哪：边界（空/单结点）先 return；排序后先清 next 再串，避免环；本地有逆序测例。
• 糙在哪：
  1. 没用链表归并，面试容易被追问「能不能少用空间」。
  2. next = cur.next 的 if/else 可一行写完。
  3. 重接用 forEach + pre 可，用普通 for 往往更直观。

正确性够用；缺的是归并模板默写。

最佳题解

自顶向下归并（推荐口述 + 默写）：

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
  if (!head || !head.next) return head;

  let slow = head;
  let fast = head.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  const mid = slow.next;
  slow.next = null;

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

function merge(l1, l2) {
  const dummy = new ListNode(0);
  let cur = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      cur.next = l1;
      l1 = l1.next;
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next;
  }
  cur.next = l1 || l2;
  return dummy.next;
}

• 时间 O(n log n)，空间 O(log n) 递归栈（相对数组 O(n) 更贴近进阶要求）。
• 为何更优：拆分靠快慢指针，合并复用「合并两有序链表」；整题就是分治 + 21。

关联题目

题	为何相关
21. 合并两个有序链表	归并的合并步骤
876. 链表的中间结点	快慢找中点
23. 合并 K 个升序链表	归并思想升级

一句话带走

排序链表：能 AC 可用数组；面试讲「快慢拆半 + 合并两有序链」——148 = 分治 × 21。