148. 排序链表 (Medium)
专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/sort-list/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你链表的头结点 head，将其按升序排列并返回排序后的链表。
进阶： 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下解决吗？
示例：
- 输入：head = [4,2,1,3]
- 输出：[1,2,3,4]
题目详细分析
- 数据范围： 链表中节点数在 [0, 5*10^4] 范围内，节点值在 [-10^5, 10^5] 范围内
- 输入特征： 单链表，无序，需要排序
- 核心约束： O(n log n) 时间和 O(1) 空间（进阶要求）——排除了插入排序 O(n^2)、也排除了自顶向下归并的 O(log n) 递归栈空间
- 隐藏条件： 数组上的 O(n log n) 排序算法（快排、归并、堆排）需要随机访问，链表不支持随机访问，所以只有「归并排序」适合链表
- 边界条件： 空链表、只有一个节点（已经有序）、所有节点值相同
小白版直白理解
就像整理一条乱序的项链，你不能像整理数组那样直接交换位置，因为只能一颗一颗地前后找。
一个有效的方法是「先拆再合」：先把项链不断对半拆开，直到每段只有一颗珠子（这时每段都是「有序」的）；然后再两两合并，合并时按大小排列。这个过程就像淘汰赛：先拆散到个人，再两两比试合并。
解题思路
思路一：自顶向下归并排序（推荐）
为什么这样想： 链表归并排序天然适合链表结构。找中点可以用快慢指针（O(n)），断开后递归排序，然后合并两个有序链表（复用 21 题）。整体 O(n log n)，但递归栈空间为 O(log n)。
关键洞察： 快慢指针找中点时，fast 初始化为 head.next 可以使 slow 停在「中间偏左」，这样 slow.next 就是右半段的头，然后将 slow.next 断开。
def sortList(head):
"""自顶向下归并排序"""
if not head or not head.next:
return head
# 1. 快慢指针找中点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # 右半段起点
slow.next = None # 断开为左右两段
# 2. 递归排序左右两半
left = sortList(head)
right = sortList(mid)
# 3. 合并两个有序链表
dummy = ListNode(0)
cur = dummy
while left and right:
if left.val <= right.val:
cur.next = left
left = left.next
else:
cur.next = right
right = right.next
cur = cur.next
cur.next = left if left else right
return dummy.next思路二：自底向上归并排序（进阶，O(1) 空间）
思路讲解： 从长度为 1 的子链表开始，不断两两合并，直到完整链表。每轮合并所有长度为 sub_len 的子链表，下一轮 sub_len 翻倍。通过迭代而非递归实现 O(1) 空间。实现更复杂，但满足进阶的常数空间要求。
关键洞察： 需要用循环模拟归并的多层合并过程。核心是每次将链表拆分为多个长度为 sub_len 的块，两两合并，然后 sub_len *= 2。
def sortList(head):
"""自底向上归并排序（O(1) 空间）"""
if not head or not head.next:
return head
# 计算链表长度
length = 0
cur = head
while cur:
length += 1
cur = cur.next
dummy = ListNode(0, head)
sub_len = 1
while sub_len < length:
prev = dummy
cur = dummy.next
while cur:
# 取第一段 sub_len 个节点
left = cur
right = split(left, sub_len)
cur = split(right, sub_len) # 剩余部分的头
# 合并 left 和 right
merged = merge(left, right)
prev.next = merged
# prev 移到合并后的尾部
while prev.next:
prev = prev.next
sub_len *= 2
return dummy.next
def split(head, n):
"""从 head 开始切下 n 个节点，返回剩余部分的头"""
while head and n > 1:
head = head.next
n -= 1
if not head:
return None
rest = head.next
head.next = None # 断开
return rest
def merge(left, right):
"""合并两个有序链表"""
dummy = ListNode(0)
cur = dummy
while left and right:
if left.val <= right.val:
cur.next = left
left = left.next
else:
cur.next = right
right = right.next
cur = cur.next
cur.next = left if left else right
return dummy.next思路三：转换为数组排序（不满足进阶要求）
思路讲解： 将链表值全部存入数组，对数组排序，再按顺序更新链表节点的值。简单但不满足 O(1) 空间要求。空间 O(n)。
def sortList(head):
"""数组辅助法（空间 O(n)）"""
if not head:
return None
vals = []
cur = head
while cur:
vals.append(cur.val)
cur = cur.next
vals.sort()
cur = head
for val in vals:
cur.val = val
cur = cur.next
return head易错点
- 快慢指针找中点： fast 初始化为
head.next让 slow 停在左半段的末尾，而不是中点。右半段起点是slow.next - 断开链表：
slow.next = None必须执行，否则递归时会出现无限循环 - 自顶向下的空间： 自顶向下递归的空间复杂度是 O(log n)（递归栈），不是 O(1)
- 自底向上的拆分： split 函数要小心处理剩余长度不足 n 的情况
- merge 后的 prev： 合并后 prev 需要移动到合并链表的尾部，不要忘了
- 空链表和单节点： 排序前先检查，空或只有一个节点直接返回
框架提炼
链表归并排序模板（自顶向下）：
def sort_list(head):
if not head or not head.next:
return head
# 找中点
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# 递归 + 合并
left = sort_list(head)
right = sort_list(mid)
return merge(left, right)链表归并排序模板（自底向上）： 通过 sub_len 翻倍迭代，避免递归。虽然代码更复杂，但实现了 O(1) 空间。核心操作是 split（切分链表）和 merge（合并有序链表）的反复调用。
关联题目
- 21-合并两个有序链表 — 归并排序的核心子操作，必须熟练掌握
- 23-合并K个升序链表 — K 路归并，分治或最小堆
- 876-链表的中间结点 — 快慢指针找中点的专项练习