排序链表
Sort List
把链表按升序排序，要求 O(n log n) 时间；节点可以复用。
在力扣中练习题目描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3] 输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目在范围
[0, 5 * 104]内 -105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
解题思路
归并排序 · 自顶向下
快慢指针找中点断开，递归排好两段再合并
链表不能随机访问，数组里常用的快排分区并不顺手；归并排序只需要“断开”和“合并”，正好适合链表。
先用快慢指针找中点，把链切成两段，递归排序左右两段。切到只剩一个节点时天然有序，再逐层合并。
把 [0,7) 从 mid=3 断开：左段 [0,3)，右段 [3,7)。
- depth
- 7
合并时用 dummy + tail，每次取两段中较小的头节点接到结果链；一段用完后，另一段整段接上。这个过程和第 21 题完全一样。
两段已经各自有序，合并成 [1, 7]；段边界 mid 消失。
- length
- 2
图中把链表按顺序展开成值，段标签对应 next 断开后形成的子链；C++ 里断开的动作是 slow->next = nullptr，合并在 merge 中完成。
自拟主例有两个 3，分别落在左右两段；合并时相等元素按左段优先，顺序仍然稳定。总时间 O(n log n)，递归深度 O(log n)。
易错点
- fast 初始化成 head：偶数长度时中点偏左，可能把链表切成长度差很大的两段。
- 忘记 slow->next = nullptr：左右两段仍然相连，递归无法终止。
- 合并时没有保存 next：修改当前节点后，剩余链的入口丢失。
- 返回 tail 或 dummy：应当返回 dummy.next 或合并后的头。
转数组排序 · 写回
把值搬到数组里排序，再按顺序写回节点
时间同样 O(n log n)，但需要 O(n) 额外数组，且没有练习链表拆分/合并；只适合作保底对照。
链表不支持随机访问，但 std::sort 可以处理数组。先遍历链表，把所有值复制进 vector，排序后再沿链表把值写回去。
节点本身不移动，链表结构也不变，只是每个节点的 val 被替换。实现极短，适合快速通过；代价是 O(n) 额外空间，而且没有利用链表“改指针就能重排”的特点。
如果面试要求 O(1) 额外空间或明确考察链表操作，这个方案只能作为对照。
- 1遍历链表，把值放进数组。
- 2对数组排序。
- 3再遍历链表，把排序后的值依次写回。
易错点
- 写回时重新遍历却忘了移动指针，所有值写到同一个节点。
- 节点带卫星数据时，只改 val 可能破坏节点身份，需要确认题目允许。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
head = [8,3,5,3,9,1,7]整条链先看成一个归并段；递归会不断从中间断开，直到每段只剩一个节点。
查看 C++ 代码
延伸阅读
- 归并排序的“拆分—递归—合并”与链表结构天然契合，是链表排序的标准答案。
- 自底向上归并可以把递归栈也省掉，做到 O(1) 额外空间，但边界处理更繁。