[Leetcode148] 链表排序

解法一：自顶向下归并排序- 递归

1. 不断二分链表：
• 用快慢指针找到中间节点 mid：快指针一次走两步，慢指针一次一步；快指针到头时，慢指针在中间。
• 把链表从中间 slow.next = None 切成左右两半：[head ... mid前]、[mid ... tail]。

2. 递归地给左右两半分别排序：
• 递归到底的情况就是：空链表或只有一个节点，这种天然有序，直接返回。

3. 合并两个有序链表：
• 完全复用 LeetCode 21：Merge Two Sorted Lists（合并两个有序链表）的思路
• 用两个指针分别指向 left / right，谁小就接到结果链表后面，指针往前走。

复杂度

• 时间：O(n log n)，每一层归并是 O(n)，总共 log n 层。

• 空间：O(log n)，主要是递归栈。

解法二：自底向上归并排序 - 迭代（推荐）

• 上面是先递归到底再往上合并（自顶向下）；

• 这里是从长度为 1 的小段开始，一轮轮往上合并（自底向上）。

1. 先知道链表总长度 length。

2. 维护一个子链表长度 sub_len，初始为 1。
意思是：当前这一轮我们把“长度为 1 的小块”两两合并成“长度为 2 的块”。

3. 然后下一轮 sub_len *= 2：长度为 2 的块，两两合并成长度为 4 的块。

4. 一直翻倍，直到 sub_len >= length，整个链表就完全有序了。

• 一段 head1（长度 ~ sub_len）

• 一段 head2（长度 ~ sub_len）

• 把这两个有序段归并成一段长约 2 * sub_len 的新有序段，然后接回大链表中。

• 时间：O(n log n)，每一层合并所有节点是 O(n)，总共 log n 层。

• 空间：O(1)，迭代 + 常量指针。

解法三：冒泡排序

• 外层循环：从头到尾跑很多趟；

• 内层循环：针对当前“未排序的部分”，一对一对比较相邻节点：
• 如果前面的值比后面大，就交换它们的 val；
• 一趟下来，最大值就被“气泡”到了尾部。

• 时间：O(n²)，两层循环。n 偏大就会超时。

• 空间：O(1)。

解法四：选择排序

• node_i 指向当前“未排序区间的第一个节点”；

• 从 node_i 往后扫一遍，找到值最小的节点 min_node；

• 把 node_i.val 和 min_node.val 交换；

• 然后 node_i 往后走一个，重复。

• 时间：O(n²)，每次找最小值都要跑一遍后半部分。

• 空间：O(1)。

解法五：插入排序

• 前半部分维护为有序链表 sorted；

• cur 指向“下一个要插入的节点”；

• 如果 cur.val 比 sorted 尾巴还大，那直接接在后面就行；

• 否则，需要从头（借助一个 dummy 头）往后找第一个值大于 cur.val 的位置，把 cur 插到那前面。

• 时间：O(n²)。

• 空间：O(1)。

解法六：计数排序

1. 遍历一遍链表，找到所有值的 min 和 max；

2. 开一个 counts 数组，长度约等于 max - min + 1；

3. 再遍历一遍链表，counts[val - min]++ 统计频次；

4. 最后按从小到大扫一遍 counts，把值按次数重新写回链表（偏常见的是新建节点，也可以原地重写 val）。

• 时间：O(n + k)，k 是值域大小。

• 空间：O(k)，计数数组