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 后面切开链表：

const rightHead = slow.next;
slow.next = null;

切分完成后：

head 是左半部分的头节点；
rightHead 是右半部分的头节点；
slow.next = null 负责断开左右两部分。

因此，slow 不能停在原链表的最后一个节点。否则 slow.next 本来就是 null，执行上述代码不会切断任何节点，左半部分仍然是原来的完整链表。

从两个节点的链表看区别

两个节点是递归能否结束的关键边界。假设链表为：

4 -> 2 -> null

如果让 fast = head.next：

let slow = head;      // 指向 4
let fast = head.next; // 指向 2

此时 fast.next 为 null，循环不会执行，slow 仍然停在节点 4：

slow
 ↓
 4 -> 2 -> null
      ↑
     fast

随后执行切分：

const rightHead = slow.next; // rightHead 指向 2
slow.next = null;

可以正确得到两个长度为 1 的链表：

左链表：4 -> null
右链表：2 -> null

下一层递归会命中“只有一个节点”的终止条件，因此递归能够结束。

如果让 fast = head：

let slow = head; // 指向 4
let fast = head; // 指向 4

循环会执行一次：

slow = slow.next;     // slow 指向 2
fast = fast.next.next; // fast 指向 null

这时 slow 已经停在原链表的最后一个节点。再执行切分：

const rightHead = slow.next; // null
slow.next = null;            // 原本就是 null，没有真正切断链表

切分结果实际上是：

左链表：4 -> 2 -> null  // 仍然是原来的完整链表
右链表：null

接下来调用 sortList(head) 时，传入的仍然是同一个两节点链表：

sortList(4 -> 2)
  sortList(4 -> 2)
    sortList(4 -> 2)
      sortList(4 -> 2)
        ...

递归处理的链表长度始终是 2，没有缩小到终止条件要求的 1，最终就会发生栈溢出。

奇数和偶数长度下的位置

当 fast = head.next 时，slow 的最终位置都适合直接从 slow.next 处切分：

节点数    slow 最终位置    左右链表长度
2         第 1 个节点      1 + 1
3         第 2 个节点      2 + 1
4         第 2 个节点      2 + 2
5         第 3 个节点      3 + 2

左右链表不一定完全一样长，但一定都比原链表短。这样每次递归的问题规模都会缩小，最终到达空链表或单节点链表。

所以，fast = head.next 是由当前的切分方式决定的：代码需要找到的是“左半部分的尾节点”，而不是任意意义上的中点。fast = head 并非在所有链表找中点的场景中都错误；只是如果这样初始化，就必须同时调整循环条件或切分方式，确保两个节点时也能真正断开链表。

为什么不使用数组排序

可以先遍历链表把所有值放入数组，再调用数组排序，但这种做法需要 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，否则右半部分会丢失。

#148. 排序链表

#题意

#实现思路

#为什么 fast 要初始化为 head.next

#从两个节点的链表看区别

#奇数和偶数长度下的位置

#为什么不使用数组排序

#代码实现

#复杂度分析

#关键点