好的，我们这次来详细讲解 LeetCode 第 148 题「排序链表」。

1. 题目描述

题目：给你链表的头结点 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 = []
输出：[]

要求：在 O(n log n) 时间复杂度和 常数级 空间复杂度下完成（即递归栈空间不算的话，空间复杂度 O(1)）。

2. 题目分析

2.1 排序算法选择

常见排序算法的时间复杂度：

• 冒泡、插入、选择排序：O(n²) —— 不符合。
• 归并排序、快速排序、堆排序：平均 O(n log n)。

但链表排序与数组排序不同：

• 数组的归并排序需要 O(n) 额外空间（合并两个数组）。
• 链表的归并排序可以做到 O(1) 额外空间（修改指针即可）。
• 快速排序在链表上也可以实现，但最坏情况 O(n²)，且不保证稳定，一般不用。

题目要求 O(n log n) 时间 + O(1) 空间（递归栈除外，但最好用迭代避免递归栈空间） → 最适合的是 自底向上的归并排序（迭代法）。

3. 解题思路演进

3.1 递归归并排序（不符合 O(1) 空间）

递归法思路：

1. 快慢指针找到链表中点，断开成两个链表。
2. 分别递归排序左右两半。
3. 合并两个有序链表。

但递归深度 O(log n)，栈空间 O(log n)，不符合题目严格 O(1) 空间要求（如果要求严格到忽略递归栈，则递归可用，但一般面试要求迭代）。

3.2 迭代归并排序（满足要求）

自底向上（bottom-up） 的思路：

1. 先两个两个节点排序合并（长度为 1 的子链表合并成长度为 2 的有序链表）。
2. 再四个四个合并（长度为 2 的合并成长度为 4 的有序链表）。
3. 依此类推，直到整个链表有序。

步骤：

• 用 step = 1, 2, 4, 8, ... 表示当前要合并的子链表长度。
• 每次从头开始，将链表分成若干对长度为 step 的子链表，对每对进行合并。
• 用 dummy 节点辅助记录链表头。
• 合并两个有序链表的方法与「合并两个有序链表」题目相同。

4. 详细步骤拆解

假设链表为 4 -> 2 -> 1 -> 3 -> null。

4.1 合并两个有序链表的函数

先实现 merge(l1, l2)：

• 创建 dummy 节点，tail 指向 dummy。
• 比较 l1 和 l2 的节点值，小的接在 tail 后，对应链表指针后移。
• 最后将剩余部分接上。
• 返回 dummy.next。

4.2 自底向上合并过程

初始：4 -> 2 -> 1 -> 3

step = 1：

• 第一对：[4] 和 [2] 合并 → 2 -> 4
• 第二对：[1] 和 [3] 合并 → 1 -> 3
  合并结果：2 -> 4 -> 1 -> 3

step = 2：

• 第一对：[2->4] 和 [1->3] 合并：
  比较：2 与 1 → 接 1；比较：2 与 3 → 接 2；比较：4 与 3 → 接 3；接 4。
  结果：1 -> 2 -> 3 -> 4

step = 4：没有可配对的另一段，结束。

4.3 迭代合并的实现细节

1. 获取链表长度 length。
2. step 从 1 开始，每次翻倍，直到 step >= length。
3. 每次从头开始，将链表分成若干段，每两段合并，然后接到结果链表中。
4. 用 prevTail 记录已合并部分的尾部，curr 遍历链表。

5. 代码实现（带注释）

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        # 获取链表长度
        length = 0
        p = head
        while p:
            length += 1
            p = p.next
        
        dummy = ListNode(0)
        dummy.next = head
        
        step = 1
        while step < length:
            prevTail = dummy  # 上一组合并后的尾节点
            curr = dummy.next  # 当前要处理的节点
            
            while curr:
                # 第一段链表头
                left = curr
                # 走 step 步，找到第一段末尾
                for i in range(1, step):
                    if curr.next:
                        curr = curr.next
                    else:
                        break
                # 断开第一段与后面的连接
                rightStart = curr.next
                curr.next = None
                curr = rightStart
                
                # 第二段链表头
                right = curr
                # 走 step 步，找到第二段末尾
                for i in range(1, step):
                    if curr and curr.next:
                        curr = curr.next
                    else:
                        break
                # 记录第二段后的下一个节点，并断开第二段
                nextStart = None
                if curr:
                    nextStart = curr.next
                    curr.next = None
                
                # 合并 left 和 right
                merged = self.mergeTwoLists(left, right)
                # 将合并后的链表接到 prevTail 后面
                prevTail.next = merged
                # 移动 prevTail 到合并后的链表末尾
                while prevTail.next:
                    prevTail = prevTail.next
                
                curr = nextStart  # 继续处理后续节点
            
            step *= 2  # 步长翻倍
        
        return dummy.next
    
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0)
        tail = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                tail.next = l1
                l1 = l1.next
            else:
                tail.next = l2
                l2 = l2.next
            tail = tail.next
        tail.next = l1 if l1 else l2
        return dummy.next

6. 复杂度分析

• 时间复杂度：O(n log n)
  外层循环 step 为 1, 2, 4, ... 直到 ≥ n，共 O(log n) 轮。
  每轮遍历整个链表 O(n)，合并操作也是 O(n)。
  总时间 O(n log n)。

• 空间复杂度：O(1)
  只用了几个指针变量，没有递归栈（若用递归合并则栈空间 O(log n)，但题目通常允许）。

7. 关键点总结

1. 链表排序要求 O(1) 空间时，用 自底向上归并排序。
2. 先计算链表长度，控制每次合并的子链表长度。
3. 合并两个有序链表是基础操作。
4. 注意链表断开与重连的指针操作，小心成环。
5. 用 dummy 节点简化头节点处理。

这样一步步从简单合并到整个链表排序，就能在满足要求下完成题目。