LeetCode LCR 077. 排序链表
题目描述
思路分析
解法一：自顶向下归并排序（推荐）
核心思路：
- 链表不支持随机访问，无法直接使用快速排序，但归并排序天然适合链表——合并两个有序链表是 O(n) 的经典操作。
- 第一步：找中点（快慢指针）：
slow每次走 1 步，fast每次走 2 步，fast走到末尾时slow恰好位于中点。令fast = head.next出发（而非head），使slow停在左半部分的最后一个节点，便于断链。- 第二步：断链递归：记录
mid = slow.next，再令slow.next = nil断开左右两段，分别递归排序sortList(head)和sortList(mid)。- 第三步：合并有序链表：使用虚拟头节点逐节点比较，将较小节点依次接入结果链表，即 LeetCode 21 题的经典做法。
复杂度分析：
- 时间复杂度：O(n log n)，其中 n 表示链表节点数，共 log n 层递归，每层合并操作为 O(n)
- 空间复杂度：O(log n)，其中 log n 表示递归调用栈深度
class Solution {
public ListNode sortList(ListNode head) {
// 递归终止条件：空链表或单节点链表已有序
if (head == null || head.next == null) {
return head;
}
// 快慢指针找中点：fast 从 head.next 出发，slow 最终停在左半末尾
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 记录右半起始节点，断开左右两段
ListNode mid = slow.next;
slow.next = null;
// 递归排序左右两段，再合并
return merge(sortList(head), sortList(mid));
}
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;
}
}
func sortList(head *ListNode) *ListNode {
// 递归终止条件：空链表或单节点链表已有序
if head == nil || head.Next == nil {
return head
}
// 快慢指针找中点：fast 从 head.Next 出发，slow 最终停在左半末尾
slow, fast := head, head.Next
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
// 记录右半起始节点，断开左右两段
mid := slow.Next
slow.Next = nil
// 递归排序左右两段，再合并
left := sortList(head)
right := sortList(mid)
return mergeSorted(left, right)
}
// mergeSorted 合并两个有序链表
func mergeSorted(l1, l2 *ListNode) *ListNode {
// 虚拟头节点简化边界处理
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil {
// 取较小节点接入结果链表
if l1.Val < l2.Val {
cur.Next = l1
l1 = l1.Next
} else {
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
// 将剩余节点直接接上
if l1 != nil {
cur.Next = l1
}
if l2 != nil {
cur.Next = l2
}
return dummy.Next
}
解法二：自底向上归并排序（O(1) 空间）
核心思路：
- 解法一递归调用栈占用 O(log n) 空间，若追求严格 O(1) 空间，需改用迭代的自底向上归并。
- 初始将每个节点视为长度为 1 的有序子链表，按步长
subLen = 1, 2, 4, 8, ...依次两两合并，直到步长超过链表长度。- 每轮遍历链表，按当前步长切出左右两段子链表进行合并，将合并结果拼接到已处理部分的末尾。
- 使用虚拟头节点
dummy统一处理拼接逻辑，避免频繁修改头指针。复杂度分析：
- 时间复杂度：O(n log n)，其中 n 表示链表节点数，共 log n 轮，每轮合并操作为 O(n)
- 空间复杂度：O(1)，仅使用常数个辅助指针，无递归栈开销
class Solution {
public ListNode sortList(ListNode head) {
// 计算链表长度
int length = 0;
ListNode node = head;
while (node != null) {
length++;
node = node.next;
}
ListNode dummy = new ListNode(0, head);
// 步长从 1 开始，每次翻倍，直到超过链表长度
for (int subLen = 1; subLen < length; subLen <<= 1) {
ListNode pre = dummy, cur = dummy.next;
while (cur != null) {
// 切出左半段（长度为 subLen）
ListNode head1 = cur;
for (int i = 1; i < subLen && cur.next != null; i++) {
cur = cur.next;
}
// 切出右半段（长度至多为 subLen）
ListNode head2 = cur.next;
cur.next = null;
cur = head2;
for (int i = 1; i < subLen && cur != null && cur.next != null; i++) {
cur = cur.next;
}
// 保存下一段起始位置，断开右半段
ListNode next = null;
if (cur != null) {
next = cur.next;
cur.next = null;
}
// 合并左右两段，拼接到已处理链表末尾
ListNode merged = merge(head1, head2);
pre.next = merged;
while (pre.next != null) {
pre = pre.next;
}
cur = next;
}
}
return dummy.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;
}
}
func sortList(head *ListNode) *ListNode {
// 计算链表长度
length := 0
node := head
for node != nil {
length++
node = node.Next
}
dummy := &ListNode{Next: head}
// 步长从 1 开始，每次翻倍，直到超过链表长度
for subLen := 1; subLen < length; subLen <<= 1 {
pre, cur := dummy, dummy.Next
for cur != nil {
// 切出左半段（长度为 subLen）
head1 := cur
for i := 1; i < subLen && cur.Next != nil; i++ {
cur = cur.Next
}
// 切出右半段（长度至多为 subLen）
head2 := cur.Next
cur.Next = nil
cur = head2
for i := 1; i < subLen && cur != nil && cur.Next != nil; i++ {
cur = cur.Next
}
// 保存下一段起始位置，断开右半段
var next *ListNode
if cur != nil {
next = cur.Next
cur.Next = nil
}
// 合并左右两段，拼接到已处理链表末尾
merged := mergeSorted(head1, head2)
pre.Next = merged
for pre.Next != nil {
pre = pre.Next
}
cur = next
}
}
return dummy.Next
}
// mergeSorted 合并两个有序链表
func mergeSorted(l1, l2 *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for l1 != nil && l2 != nil {
if l1.Val <= l2.Val {
cur.Next = l1
l1 = l1.Next
} else {
cur.Next = l2
l2 = l2.Next
}
cur = cur.Next
}
if l1 != nil {
cur.Next = l1
}
if l2 != nil {
cur.Next = l2
}
return dummy.Next
}
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 21. 合并两个有序链表 | 简单 | 归并的核心子步骤 |
| 23. 合并 K 个升序链表 | 困难 | 归并 + 优先队列 |
| 912. 排序数组 | 中等 | 数组版归并排序 |
| 147. 对链表进行插入排序 | 中等 | 链表排序变体 |
| 1669. 合并两个链表 | 中等 | 链表合并操作 |
| 剑指 Offer II 078. 合并排序链表 | 困难 | 多链表归并 |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！