算法148. 排序链表

题目：

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

解法：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # 链表的中间节点（快慢指针法）
    def middleNode(self,head:Optional[ListNode])->Optional[ListNode]:
        if not head:
            return None
        slow=head
        fast=head

        while fast and fast.next:
            pre = slow
            slow=slow.next
            fast=fast.next.next
        pre.next = None # 断开slow的前一个节点和slow节点，拆分成两个链表
        return slow
    
    # 合并两个有序链表（双指针）
    def mergeTwoLists(self,list1:Optional[ListNode],list2:Optional[ListNode])->Optional[ListNode]:
        # 用哑节点标记链表头节点
        cur = dummy = ListNode()
        # 遍历两个有序链表，直到其中一个遍历完
        while list1 and list2:
            if list1.val >= list2.val:
                cur.next=list2
                list2=list2.next
            else:
                cur.next=list1
                list1=list1.next
            cur=cur.next
        # 将没有遍历完的拼接到最后
        cur.next=list1 if list1 else list2
        return dummy.next
    # 排序链表
    def sortList(self,head:Optional[ListNode])->Optional[ListNode]:
        # 如果链表为空或者只有一个节点，无需排序
        if head is None or head.next is None:
            return head
        
        # 找到中间节点head2，并断开head2与其前一个节点的联接
        head2 = self.middleNode(head)
        # 分治,比如把[4,2,1,3]拆成[4,2]和[1,3]，然后把[4,2]拆成[4][2]，[1,3]拆成[1][3]
        head = self.sortList(head)
        head2 = self.sortList(head2)

        #合并
        return self.mergeTwoLists(head,head2)

解析：

这段代码是链表的归并排序（Merge Sort）实现，非常经典！我们来逐行讲解，重点剖析 sortList 中的递归逻辑，以及整个流程是如何运作的。

🌟 总体结构

这是一个典型的 分治算法（Divide and Conquer）：

1. 分：用快慢指针找到链表中点，把链表从中间断开成两部分。
2. 治：对左右两部分分别递归排序。
3. 合：将两个有序链表合并成一个有序链表（调用 mergeTwoLists）。

最终返回排好序的链表头。

✅ 三个函数的作用

1. middleNode(head)：找链表中点并断开前连接

def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
        pre = slow      # 记录 slow 的前一个节点
        slow = slow.next
        fast = fast.next.next
    pre.next = None     # 断开连接
    return slow         # 返回中间节点作为右半部分的头

🔍 作用：

• 找到链表的中间节点（偏右的那个，比如偶数长度时返回第 2 个）
• 并且 断开左半部分和右半部分的连接

📌 举个例子：

输入：4 -> 2 -> 1 -> 3

执行过程：

slow 和 fast 从 head=4 开始

第1步：
  slow=4, pre=None
  slow=2, fast=1

第2步：
  pre=2, slow=1, fast=None → 结束

pre.next = None → 2.next = None

结果：

• 原链表被断成：
  • 左半：4 -> 2
  • 返回 slow=1，即右半：1 -> 3

✅ 所以这个函数不仅“找中点”，还完成了“分割”任务！

⚠️ 注意：pre 是在循环中动态记录 slow 的前驱，这样才能断开。

2. mergeTwoLists(list1, list2)：合并两个有序链表

标准写法，使用哨兵节点：

def mergeTwoLists(self, list1, list2) -> ListNode:
    cur = dummy = ListNode()
    while list1 and list2:
        if list1.val < list2.val:
            cur.next = list1
            list1 = list1.next
        else:
            cur.next = list2
            list2 = list2.next
        cur = cur.next
    cur.next = list1 or list2  # 接上剩余部分
    return dummy.next

✅ 这个函数保证：给两个有序链表，返回一个合并后的有序链表。

3. sortList(head)：主函数，递归实现归并排序

def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # 终止条件：空或只有一个节点
    if head is None or head.next is None:
        return head

    # 分：找到中点，并断开
    head2 = self.middleNode(head)

    # 治：递归排序左右两部分
    head = self.sortList(head)      # 排序左半
    head2 = self.sortList(head2)    # 排序右半

    # 合：合并两个有序链表
    return self.mergeTwoLists(head, head2)

🧠 重点：sortList 的递归是怎么运行的？

我们用一个例子来 trace：4 -> 2 -> 1 -> 3

🌲 第一层递归（原始调用）

head = 4 -> 2 -> 1 -> 3

1. 调用 middleNode(head)：

   • 返回 head2 = 1 -> 3
   • 原链表变成：4 -> 2（因为 pre.next = None）

2. 递归调用：

   head = sortList(4 -> 2)
   head2 = sortList(1 -> 3)
   

🔁 第二层递归：sortList(4 -> 2)

head = 4 -> 2

1. middleNode(4 -> 2)：

   • slow 会走到 2，pre = 4
   • pre.next = None → 4.next = None
   • 返回 head2 = 2

2. 现在：

   • head = 4（单节点）
   • head2 = 2（单节点）

3. 递归调用：

   sortList(4) → 返回 4
   sortList(2) → 返回 2
   

4. 合并：mergeTwoLists(4, 2) → 返回 2 -> 4

✅ 所以 sortList(4 -> 2) 返回 2 -> 4

🔁 第二层递归：sortList(1 -> 3)

类似地：

1. middleNode(1 -> 3)：

   • 返回 head2 = 3，原链表断开为 1 和 3

2. 递归：

   • sortList(1) → 返回 1
   • sortList(3) → 返回 3

3. 合并：mergeTwoLists(1, 3) → 返回 1 -> 3

✅ 所以 sortList(1 -> 3) 返回 1 -> 3

🔚 第一层合并

现在回到第一层：

head = 2 -> 4
head2 = 1 -> 3

调用：

mergeTwoLists(2->4, 1->3)

合并过程：

• 比较 2 和 1 → 取 1
• 比较 2 和 3 → 取 2
• 比较 4 和 3 → 取 3
• 最后接上 4

结果：1 -> 2 -> 3 -> 4

✅ 完美排序！

📌 递归树可视化

                 [4,2,1,3]
                /         \
           [4,2]           [1,3]
           /    \           /    \
         [4]    [2]       [1]    [3]
           \     /          \     /
        merge(2,4)       merge(1,3)
               \             /
           merge(2->4, 1->3)
                    |
             [1->2->3->4]

🧩 关键点解析

1. 为什么 middleNode 要返回 slow 并断开 pre.next？

• slow 是右半部分的头
• pre.next = None 是为了断开左右两部分，避免递归时无限循环
• 否则 sortList(head) 还是整个链表，无法真正“分”

2. 递归终止条件是什么？

if head is None or head.next is None:
    return head

• 空链表或单节点 → 已经有序 → 直接返回

3. 为什么可以递归调用 sortList(head)？

因为 middleNode 已经把 head 所在的链表从中间断开了，现在 head 指向的是左半部分，长度减半，递归下去一定会到达终止条件。

4. 时间复杂度？

• 每层 O(n) 合并
• 递归深度 O(log n)
• 总体：O(n log n)

5. 空间复杂度？

• 递归栈深度 O(log n)
• 链表本身不额外分配节点
• 所以是 O(log n)（递归栈空间）

✅ 总结

💡 小技巧记忆

链表归并排序 = 快慢找中 + 断开 + 递归 + 合并

就像切面条：

1. 一刀从中间切开（middleNode）
2. 左右分别再切，直到变成一根（递归到底）
3. 然后从小到大一根根合并回去（merge）