知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 08 - 排序链表 ## 题目(LeetCode 148) 在 O(n log n) 时间和 O(1) 空间下对链表排序。 ## 大白话理解 链表排序最适合归并排序:快慢指针找中点 → 断开 → 分别排序 → 合并。 ## 代码 ```java public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; // 1. 快慢指针找中点 ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } // 2. 从中点断开 ListNode mid = slow.next; slow.next = null; // 3. 递归排序两半 ListNode left = sortList(head); ListNode right = sortList(mid); // 4. 合并两个有序链表(复用第 02 题的逻辑) return merge(left, right); } private ListNode merge(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode curr = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; } else { curr.next = l2; l2 = l2.next; } curr = curr.next; } curr.next = (l1 != null) ? l1 : l2; return dummy.next; } ``` 注意 `fast = head.next` 而不是 `fast = head`,这样中点偏左,断开后左半段不会包含中点。 ## 一句话总结 归并排序三步:快慢指针找中点、断开、合并。合并就是第 02 题。 --- 上一篇:[07 - K个一组翻转](./07-reverse-k-group.md) | 下一篇:[09 - LRU缓存](./09-lru-cache.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入