好的，我们这次来详细讲解 LeetCode 第 148 题：排序链表（Sort List）。

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) 时间复杂度和常数级空间复杂度下解决这个问题吗？

2. 题目分析

链表排序的常见方法有：

1. 转换成数组排序再转回链表
   • 时间 O(n log n)，空间 O(n)（不符合进阶要求）
2. 归并排序（自顶向下递归）
   • 时间 O(n log n)，空间 O(log n)（递归栈空间）
3. 归并排序（自底向上迭代）
   • 时间 O(n log n)，空间 O(1)（满足进阶要求）

我们重点讲解 自底向上归并排序，因为它满足题目进阶的常数空间要求。

3. 自底向上归并排序思路

归并排序的核心思想是：

• 先让最小的子段（长度为 1）有序，然后两两合并成长度为 2 的有序段，再合并成长度为 4 的有序段……直到整个链表有序。

步骤：

1. 获取链表长度 length。
2. 设置子段长度 step，从 1 开始，每次翻倍，直到 step >= length。
3. 每次将链表分成若干段，每段长度约 step，然后两两合并。
4. 合并两个有序链表是经典操作，用双指针法。
5. 用 dummy 节点简化头节点处理。

4. 详细步骤拆解

4.1 获取链表长度

def getLength(head):
    length = 0
    while head:
        length += 1
        head = head.next
    return length

4.2 合并两个有序链表

def merge(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

4.3 自底向上归并主循环

• step = 1, 2, 4, ...
• 每次从头开始，将链表分成若干对长度为 step 的子链表，合并每一对。
• 用 prev_tail 记录上一组合并后的尾节点，用于连接下一组合并结果。

关键细节：

• cut(l, n) 函数：从链表 l 开始切下前 n 个节点，返回剩余链表的头。
• 合并后，将合并好的子链表接在上一次合并的尾部。

5. 完整代码（Python）

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:
            prev_tail = dummy  # 上一组合并后的尾节点
            curr = dummy.next  # 当前要处理的节点
            
            while curr:
                # 切下第一段
                left = curr
                for _ in range(1, step):
                    if curr.next:
                        curr = curr.next
                    else:
                        break
                right_start = curr.next
                curr.next = None  # 断开
                curr = right_start
                
                # 切下第二段
                right = curr
                for _ in range(1, step):
                    if curr and curr.next:
                        curr = curr.next
                    else:
                        break
                if curr:
                    next_start = curr.next
                    curr.next = None  # 断开
                    curr = next_start
                else:
                    next_start = None
                
                # 合并 left 和 right
                merged = self.mergeTwoLists(left, right)
                # 将合并结果接到 prev_tail 后面
                prev_tail.next = merged
                # 移动 prev_tail 到合并后的链表尾部
                while prev_tail.next:
                    prev_tail = prev_tail.next
                # 连接剩余部分
                prev_tail.next = next_start
                curr = next_start
            
            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 翻倍，最多 log n 次；每次遍历整个链表 O(n)。
• 空间复杂度：O(1)
  只用了常数个额外指针。

7. 总结

这道题的关键是 将归并排序应用于链表，并且用自底向上的迭代方式避免递归栈空间，达到 O(1) 空间复杂度。
合并有序链表是基础操作，切分链表时注意边界处理（链表长度不足 step 的情况）。

如果你对某一部分还有疑问，我可以进一步展开讲解。