【LeetHOT100】排序链表——Java多解法详解
·
一、题目描述
148. 排序链表
给你链表的头结点 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 * 10⁴]内 -
-10⁵ <= Node.val <= 10⁵
进阶： 你可以在 O(n log n) 时间复杂度和 O(1) 空间复杂度下排序链表吗？
二、解题思路概览
链表排序比数组排序要麻烦，因为无法像数组那样通过下标随机访问。常见解法有四种：
| 解法 | 时间复杂度 | 空间复杂度 | 特点 | 面试推荐 |
|---|---|---|---|---|
| 归并排序（递归） | O(n log n) | O(log n) | 稳定，逻辑清晰 | ⭐⭐⭐⭐⭐ |
| 归并排序（迭代） | O(n log n) | O(1) | 满足进阶要求 | ⭐⭐⭐⭐⭐ |
| 快速排序 | 平均 O(n log n)，最坏 O(n²) | O(log n) | 链表实现复杂，易超时 | ⭐⭐ |
| 计数排序 | O(n + k) | O(k) | 值域受限时极快 | ⭐⭐⭐（特定场景） |
最佳选择：归并排序。因为链表归并时不需要额外数组空间（合并两个有序链表只需要 O(1) 空间），天然适合链表。
三、解法一：归并排序（递归 + 快慢指针）⭐
3.1 核心思路
归并排序的核心是 分治：
-
分割（找中点）：使用快慢指针找到链表的中点，将链表分成左右两半
-
递归排序：分别对左右两半递归调用排序函数
-
合并：将两个有序链表合并成一个有序链表
3.2 代码实现
java
class Solution {
public ListNode sortList(ListNode head) {
// 递归终止条件：空链表或只有一个节点
if (head == null || head.next == null) {
return head;
}
// 1. 使用快慢指针找中点
ListNode slow = head;
ListNode fast = head;
ListNode prev = null; // 记录 slow 的前驱，用于切断链表
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
// 2. 切断链表，分成 left 和 right 两半
prev.next = null;
ListNode left = head;
ListNode right = slow;
// 3. 递归排序左右两半
left = sortList(left);
right = sortList(right);
// 4. 合并两个有序链表
return merge(left, right);
}
// 合并两个有序链表（迭代版）
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
3.3 图解示例
以 head = [4,2,1,3] 为例：
text
步骤1：找中点分割
原链表: 4 → 2 → 1 → 3 → null
↑
slow (中点)
切断后: left: 4 → 2 → null
right: 1 → 3 → null
步骤2：递归排序 left
left: 4 → 2 → null
分割: left-left: 4 → null, left-right: 2 → null
合并: 2 → 4 → null
步骤3：递归排序 right
right: 1 → 3 → null
分割: right-left: 1 → null, right-right: 3 → null
合并: 1 → 3 → null
步骤4：合并左右结果
left: 2 → 4 → null
right: 1 → 3 → null
合并: 1 → 2 → 3 → 4 → null
3.4 复杂度分析
-
时间复杂度：O(n log n)。归并排序的递归深度为 log n，每层合并的总时间复杂度为 O(n)
-
空间复杂度：O(log n)。递归调用栈的深度为 log n
四、解法二：归并排序（迭代 / 自底向上）⭐⭐⭐
4.1 核心思路
递归版本需要 O(log n) 的栈空间。如果要求严格的 O(1) 空间，可以使用自底向上的归并排序：
-
先确定链表的长度
length -
从步长
step = 1开始，将链表分成若干个长度为step的小段，每两段进行合并 -
步长翻倍，重复步骤 2，直到
step >= length
4.2 代码实现
java
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// 1. 计算链表长度
int length = 0;
ListNode p = head;
while (p != null) {
length++;
p = p.next;
}
ListNode dummy = new ListNode(0, head);
// 2. 自底向上归并
for (int step = 1; step < length; step <<= 1) {
ListNode prev = dummy;
ListNode cur = dummy.next;
while (cur != null) {
// 找到第一段的头 left，长度为 step
ListNode left = cur;
// 找到第二段的头 right，长度为 step
ListNode right = cut(left, step);
// 找到下一段的头（right 段之后的部分）
ListNode next = cut(right, step);
// 合并 left 和 right 两段
prev.next = merge(left, right);
// 移动 prev 到合并后的尾部
while (prev.next != null) {
prev = prev.next;
}
// 移动 cur 到下一段
cur = next;
}
}
return dummy.next;
}
// 切断链表：将链表从头开始的前 step 个节点切出来，返回剩余部分的头节点
private ListNode cut(ListNode head, int step) {
if (head == null) return null;
ListNode p = head;
// 找到第 step 个节点（从1开始计数）
for (int i = 1; i < step && p.next != null; i++) {
p = p.next;
}
ListNode next = p.next;
p.next = null; // 切断
return next;
}
// 合并两个有序链表
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
4.3 图解示例（step 合并过程）
以 [4,2,1,3]，step = 1 为例：
text
原始: 4 → 2 → 1 → 3 → null step=1: 第一轮: left=[4], right=[2] → merge → [2,4] 第二轮: left=[1], right=[3] → merge → [1,3] 结果: 2 → 4 → 1 → 3 → null step=2: 第一轮: left=[2,4], right=[1,3] → merge → [1,2,3,4] 结果: 1 → 2 → 3 → 4 → null step=4: step >= length，结束
4.4 复杂度分析
-
时间复杂度：O(n log n)，每层合并 O(n)，共 log n 层
-
空间复杂度：O(1)，只使用了常数个指针
五、解法三：快速排序（链表版）
5.1 核心思路
链表快排的核心是用头节点作为基准，遍历分割，递归处理。
5.2 代码实现（交换节点值）
java
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
quickSort(head, null);
return head;
}
private void quickSort(ListNode head, ListNode tail) {
if (head == tail || head.next == tail) return;
ListNode pivot = partition(head, tail);
quickSort(head, pivot);
quickSort(pivot.next, tail);
}
private ListNode partition(ListNode head, ListNode tail) {
int pivotVal = head.val;
ListNode left = head;
ListNode cur = head.next;
while (cur != tail) {
if (cur.val < pivotVal) {
left = left.next;
swap(left, cur);
}
cur = cur.next;
}
swap(head, left);
return left;
}
private void swap(ListNode a, ListNode b) {
int temp = a.val;
a.val = b.val;
b.val = temp;
}
}
5.3 快排为什么容易超时？
LeetCode 148 的测试用例包含大量已排序或近似排序的链表，当选择头节点作为基准时：
-
已排序链表会退化成 O(n²)
-
50000 个节点的 O(n²) ≈ 12.5 亿次操作 → 必然超时
5.4 改进方案（三路快排 + 选中间节点作基准）
java
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
return quickSort(head);
}
private ListNode quickSort(ListNode head) {
if (head == null || head.next == null) return head;
// 选择中间节点作为基准（避免最坏情况）
ListNode pivotNode = getMiddle(head);
int pivot = pivotNode.val;
ListNode leftDummy = new ListNode(0);
ListNode rightDummy = new ListNode(0);
ListNode midDummy = new ListNode(0);
ListNode left = leftDummy, right = rightDummy, mid = midDummy;
ListNode cur = head;
while (cur != null) {
if (cur.val < pivot) {
left.next = cur;
left = left.next;
} else if (cur.val == pivot) {
mid.next = cur;
mid = mid.next;
} else {
right.next = cur;
right = right.next;
}
cur = cur.next;
}
left.next = null;
mid.next = null;
right.next = null;
ListNode sortedLeft = quickSort(leftDummy.next);
ListNode sortedRight = quickSort(rightDummy.next);
return concat(sortedLeft, midDummy.next, sortedRight);
}
private ListNode getMiddle(ListNode head) {
if (head == null) return null;
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
private ListNode concat(ListNode left, ListNode mid, ListNode right) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
if (left != null) {
cur.next = left;
while (cur.next != null) cur = cur.next;
}
if (mid != null) {
cur.next = mid;
while (cur.next != null) cur = cur.next;
}
cur.next = right;
return dummy.next;
}
}
六、解法四：计数排序（值域受限时极快）
6.1 核心思路
由于题目中节点值的范围是 -10⁵ <= val <= 10⁵，我们可以使用计数排序，时间复杂度 O(n + k)，其中 k = 200001。
6.2 代码实现
java
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
// 1. 找出最大值和最小值
int max = head.val;
int min = head.val;
ListNode cur = head;
while (cur != null) {
max = Math.max(max, cur.val);
min = Math.min(min, cur.val);
cur = cur.next;
}
// 2. 计数数组
int range = max - min + 1;
int[] count = new int[range];
cur = head;
while (cur != null) {
count[cur.val - min]++;
cur = cur.next;
}
// 3. 回写链表
cur = head;
for (int i = 0; i < range; i++) {
while (count[i]-- > 0) {
cur.val = i + min;
cur = cur.next;
}
}
return head;
}
}
6.3 复杂度分析
-
时间复杂度：O(n + k)，当 k ≈ n 时接近 O(n)
-
空间复杂度：O(k)，k = 200001，约 200KB
七、解法对比与总结
| 方法 | 时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 | 面试推荐 |
|---|---|---|---|---|---|
| 归并排序（递归） | O(n log n) | O(log n) | ✅ | 通用 | ⭐⭐⭐⭐⭐ |
| 归并排序（迭代） | O(n log n) | O(1) | ✅ | 严格要求O(1)空间 | ⭐⭐⭐⭐⭐ |
| 快速排序 | 平均 O(n log n) | O(log n) | ❌ | 链表已排序时易超时 | ⭐⭐ |
| 计数排序 | O(n + k) | O(k) | ✅ | 值域范围小 | ⭐⭐⭐ |
八、面试建议
8.1 标准答案（归并排序递归版）
这是面试官最期望看到的答案：
java
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
// 快慢指针找中点
ListNode slow = head, fast = head, prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
ListNode left = sortList(head);
ListNode right = sortList(slow);
return merge(left, right);
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
8.2 常见错误
-
切断链表时忘记设
prev.next = null：导致左右链表没有真正分离，递归会进入死循环 -
快慢指针找中点时的边界条件：要处理偶数长度和奇数长度两种情况
-
合并链表时不要创建新节点：直接修改
next指针即可，复用原有节点
8.3 如果面试官问快排
“快排对链表的时间复杂度平均 O(n log n)，但最坏情况 O(n²)。LeetCode 上有大量有序链表的测试用例，快排可能超时。我可以选择中间节点作为基准来优化，但更推荐归并排序，因为它最坏情况也是 O(n log n)。”
九、相关链接
-
官方题解：排序链表官方题解
-
LeetCode Hot 100 汇总：力扣热题100题
更多推荐
10
0- 0
已为社区贡献9条内容
所有评论(0)