148. 排序链表

题意

给定链表的头节点 head，请将链表按升序排列，并返回排序后的链表。要求时间复杂度为 O(nlogn)，并尽量使用常数级额外空间。

实现思路

链表不能像数组一样随机访问，无法高效地通过下标定位元素，因此更适合使用归并排序。归并排序只需要顺序遍历链表，且合并两个有序链表时可以直接调整节点指针：

使用快慢指针找到链表中点，将链表拆成左右两段。
分别递归排序左右两段链表。
将两个有序链表合并成一个有序链表。
递归终止条件是链表为空，或者链表只有一个节点。

例如链表 4 -> 2 -> 1 -> 3 的拆分过程如下：

4 -> 2 -> 1 -> 3
       /       \
   4 -> 2     1 -> 3
   /   \      /   \
  4     2    1     3

叶子链表天然有序，之后逐层合并即可得到 1 -> 2 -> 3 -> 4。

选择 fast = head.next 的原因是：拆分时需要让 slow 停在左半部分的尾节点，而不是仅仅找到一个“中间节点”。这样执行 slow.next = null 后，左右链表的长度都会变小，递归才能结束。

为什么不使用数组排序

可以先遍历链表把所有值放入数组，再调用数组排序，但这种做法需要 O(n) 的额外空间，也没有利用链表本身适合顺序合并的特点。直接对链表做归并排序可以复用原节点，避免重新创建业务节点。

代码实现

// sortList 函数接收链表头节点 head，返回排序后的链表头节点
var sortList = function (head) {
  // 如果链表为空，或者链表只有一个节点，说明已经有序，直接返回
  if (head === null || head.next === null) {
    // 返回当前链表头节点，作为递归的终止结果
    return head;
  }

  // slow 是慢指针，用来寻找链表中点，初始指向头节点
  let slow = head;
  // fast 是快指针，每次走两步；从 head.next 开始可以让 slow 停在左半部分的尾节点
  let fast = head.next;

  // 当 fast 还能继续向后走时，说明 slow 还没有到达中间位置
  while (fast !== null && fast.next !== null) {
    // slow 每次只走一步
    slow = slow.next;
    // fast 每次走两步
    fast = fast.next.next;
  }

  // slow.next 是右半部分链表的头节点，需要先保存下来
  const rightHead = slow.next;
  // 将 slow.next 置为 null，把原链表断开成左右两个独立链表
  slow.next = null;

  // 递归排序左半部分链表，head 仍然是左半部分的头节点
  const left = sortList(head);
  // 递归排序右半部分链表，rightHead 是右半部分的头节点
  const right = sortList(rightHead);

  // 将两个已经有序的链表合并，并返回合并后的头节点
  return merge(left, right);
};

// merge 函数接收两个升序链表 list1 和 list2，返回合并后的升序链表
function merge(list1, list2) {
  // 创建虚拟头节点，方便统一处理结果链表的第一个节点
  const dummy = new ListNode(0);
  // cur 指向结果链表的尾节点，后续新接入的节点都挂在 cur.next 上
  let cur = dummy;

  // 当两个链表都还有节点时，持续比较两个链表当前节点的值
  while (list1 !== null && list2 !== null) {
    // 如果 list1 当前节点的值更小或相等，就把 list1 当前节点接到结果链表后面
    if (list1.val <= list2.val) {
      // cur.next 指向 list1 当前节点，完成节点拼接
      cur.next = list1;
      // list1 指针后移，准备比较 list1 的下一个节点
      list1 = list1.next;
    } else {
      // 否则说明 list2 当前节点更小，就把 list2 当前节点接到结果链表后面
      // cur.next 指向 list2 当前节点，完成节点拼接
      cur.next = list2;
      // list2 指针后移，准备比较 list2 的下一个节点
      list2 = list2.next;
    }

    // cur 后移到结果链表的最新尾节点
    cur = cur.next;
  }

  // 循环结束后，至少有一个链表已经为空；另一个链表剩余部分本身已经有序，直接接上即可
  cur.next = list1 === null ? list2 : list1;

  // dummy 是虚拟头节点，真正的排序结果从 dummy.next 开始
  return dummy.next;
}

复杂度分析

时间复杂度：O(nlogn)。链表会被拆分为 logn 层，每一层合并时总共遍历 n 个节点。
空间复杂度：O(logn)，来自递归调用栈；合并过程只使用了常数个指针，并没有新建业务节点。
稳定性：合并时使用 list1.val <= list2.val，相同值优先取左链表节点，因此排序是稳定的。

如果需要严格的 O(1) 额外空间，可以改用自底向上的迭代归并排序：从长度为 1 的有序子链表开始，两两合并，再将子链表长度扩大为 2、4、8...。本题常见的递归写法更直观，面试中应根据题目是否强调常数级空间来选择实现。

关键点

找中点时让 fast 从 head.next 开始，可以保证 slow 停在左半部分的尾节点，方便执行 slow.next = null 切断链表。
这里不是单纯为了找到“中间节点”，而是为了找到“左半部分的尾节点”。如果 fast 从 head 开始，两个节点的链表中 slow 会停在最后一个节点，导致 rightHead = slow.next 为 null，链表没有被真正拆开，递归会一直处理同一段链表。
例如链表 4 -> 2，让 fast = head.next 时，循环不会执行，slow 停在 4，可以拆成 4 和 2 两段；这能保证递归规模持续变小。
合并时直接复用原链表节点，不需要创建新的业务节点，只需要一个虚拟头节点辅助拼接。
必须先保存 rightHead = slow.next，再断开 slow.next，否则右半部分会丢失。

ON THIS PAGE

#148. 排序链表

#题意

#实现思路

#为什么不使用数组排序

#代码实现

#复杂度分析

#关键点

148. 排序链表

题意

实现思路

为什么不使用数组排序

代码实现

复杂度分析

关键点