链表中等1 种解法
#148排序链表
使用适合链表的归并排序，在 O(n log n) 时间内按升序排列节点。
#链表#归并排序#双指针
原题
给你链表的头结点 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 * 104]内 -105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
解题主线
- fast 从 head.next 出发，使偶数长度时 slow 停在前半段尾节点，确保能正确断链。
- 链表合并只修改 next，不需要数组搬移元素。
解法 1：自顶向下归并排序
快慢指针二分链表，分别递归排序左右半段，再线性合并。
-
时间复杂度： O(n log n)
-
空间复杂度： O(log n)（递归栈）
public class Solution {
static final class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode sortList(ListNode head) {
// 长度小于 2 的链表天然有序，也是递归能够收敛的边界。
if (head == null || head.next == null) return head;
ListNode slow = head;
ListNode fast = head.next;
// fast 从第二个节点出发，使 slow 最终停在前半段尾节点。
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rightHead = slow.next;
// 断开左右半段，确保两次递归的输入规模都严格缩小。
slow.next = null;
return merge(sortList(head), sortList(rightHead));
}
private ListNode merge(ListNode left, ListNode right) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (left != null && right != null) {
if (left.val <= right.val) {
tail.next = left;
left = left.next;
} else {
tail.next = right;
right = right.next;
}
tail = tail.next;
}
tail.next = left != null ? left : right;
return dummy.next;
}
}边界与易错点
- 若 fast 与 slow 都从 head 出发且直接在 slow 后断链，两节点输入可能无法缩小递归规模。
- 自顶向下归并会占用 O(log n) 递归栈，不能标为严格 O(1) 额外空间。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
Q148_linkedList_sort_list.java