知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 41 - 排序链表 ## 题目(LeetCode 148) 对链表进行排序,要求 O(n log n) 时间和 O(1) 空间。 ## 解法:归并排序 ```java class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; // 找中点 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; // 递归排序两半 ListNode left = sortList(head); ListNode right = sortList(mid); // 合并 return merge(left, right); } private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0), 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; } } ``` ## 复杂度 - 时间 O(n log n),空间 O(log n) 递归栈 ## 一句话总结 链表归并排序:找中点断开,递归排序两半,合并。 ## 关于快速排序 链表也可以用快速排序,但有明显劣势: - 链表不支持随机访问,找 pivot 和 partition 都需要 O(n) 遍历 - 最坏情况 O(n²),且链表的 pivot 随机化成本高 - 无法像数组那样利用缓存局部性 因此**链表排序首选归并排序**,它天然适合链表的顺序访问特性。 ## 解法二:自底向上归并(真正 O(1) 空间) 递归版本有 O(log n) 的调用栈,迭代版本可以做到真正的 O(1) 空间。 ```java class Solution { public ListNode sortList(ListNode head) { int len = 0; ListNode node = head; while (node != null) { len++; node = node.next; } ListNode dummy = new ListNode(0); dummy.next = head; for (int size = 1; size < len; size <<= 1) { ListNode cur = dummy.next, tail = dummy; while (cur != null) { ListNode left = cur; ListNode right = split(left, size); cur = split(right, size); ListNode[] merged = merge(left, right); tail.next = merged[0]; tail = merged[1]; } } return dummy.next; } // 从 head 开始截取 n 个节点,返回剩余部分 private ListNode split(ListNode head, int n) { while (--n > 0 && head != null) head = head.next; if (head == null) return null; ListNode rest = head.next; head.next = null; return rest; } // 合并两个链表,返回 [头, 尾] private ListNode[] merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0), 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; while (cur.next != null) cur = cur.next; return new ListNode[]{dummy.next, cur}; } } ``` ## 解法对比 | | 解法一(递归归并) | 解法二(迭代归并) | |--|--------|--------| | 时间复杂度 | O(n log n) | O(n log n) | | 空间复杂度 | O(log n)(递归栈) | O(1) | | 特点 | 代码简洁 | 严格满足题目 O(1) 空间要求 |
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入