排序链表

题目描述
给你一个链表的头节点 head，请将其按升序排列，并返回排序后的链表。链表节点的定义通常为：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

要求时间复杂度在 O(n log n) 范围内，且空间复杂度最好为 O(1) 或 O(log n)。

解题过程

1. 问题分析

• 链表排序的难点在于不能像数组那样随机访问元素，因此像快速排序这类依赖随机访问的算法不太适用。
• 时间复杂度要求 O(n log n) 提示我们使用归并排序或堆排序，但堆排序在链表中实现较复杂。
• 归并排序非常适合链表，因为链表的合并操作可以在 O(1) 的额外空间内完成。

2. 算法选择：归并排序（递归版）
归并排序的核心思想是分治：

1. 分割：找到链表的中点，将链表分成两半。
2. 递归：分别对两半链表进行排序。
3. 合并：将两个已排序的链表合并成一个有序链表。

3. 关键步骤详解

步骤 3.1：找到链表中点（快慢指针法）

• 使用快慢指针：慢指针每次走一步，快指针每次走两步。当快指针到达末尾时，慢指针正好在中点。
• 注意：需要记录中点的前一个节点，以便切断链表。
• 示例：链表 4→2→1→3，慢指针最终停在 2，将其与后部分切断，得到 4→2 和 1→3。

步骤 3.2：递归排序左右两部分

• 对分割后的两个子链表递归调用排序函数。
• 递归终止条件：链表为空或只有一个节点（直接返回）。

步骤 3.3：合并两个有序链表

• 创建一个哑节点（dummy）作为新链表的头部。
• 比较两个链表当前节点的值，将较小者接入新链表。
• 重复直到某一链表为空，将另一链表剩余部分直接接上。

4. 代码实现示例（Python）

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        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 = self.sortList(head)
        right = self.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

5. 复杂度分析

• 时间复杂度：O(n log n)，每层分割和合并共 O(n)，递归深度为 O(log n)。
• 空间复杂度：O(log n)，主要用于递归调用栈（若用迭代版可优化至 O(1)）。

6. 关键点总结

• 快慢指针找中点时，注意初始设置 fast = head.next 可避免无限递归（如两节点时）。
• 合并操作是链表归并排序的核心，需熟练掌握哑节点的使用。