148. 排序链表

题目链接：148. 排序链表

题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

你可以在 $O(n \log n)$ 时间复杂度和常数级空间复杂度（不考虑递归栈的开销）下解决这个问题吗？

核心思考：链表归并排序 (Merge Sort)

要达到 $O(n \log n)$ 的时间复杂度，最经典且适合链表结构的算法是归并排序。

1. 分割阶段（Divide）：
   • 使用**快慢指针（Fast & Slow Pointers）**来寻找链表的中间节点。
   • 关键操作：在找到中间节点后，必须将前一半链表的结尾指针（即 pre.next）置为空。这一步彻底将长链表单向解耦成两个互不相干的独立子链表。
   • 递归地对这两个子链表继续进行分割，直到链表长度为 0 或 1。
2. 合并阶段（Conquer & Merge）：
   • 我们拥有两个已经局部有序的子链表 list1 和 list2。
   • 使用辅助节点 dummy 建立一个新链表，通过双指针比较大小，按从小到大的顺序将节点逐个挂载。
   • 最后将剩余未遍历完的子链表直接连接到新链表的末尾。

这种方法充分利用了链表“不需要物理连续存储”和“易于重新挂载”的特性，比快速排序等在链表上表现更稳定。

解题思路 (Python)

# 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 head is None or head.next is None:
            return head
        
        # 1. 分割：利用快慢指针找到中点并切断
        head2 = self.mid_node(head)

        # 2. 递归：分别对左右两侧进行排序
        head = self.sortList(head)
        head2 = self.sortList(head2)

        # 3. 合并：将两个有序链表合并为一个
        return self.merge(head, head2)

    def mid_node(self, head):
        slow = fast = head
        pre = None
        while fast and fast.next:
            pre = slow
            slow = slow.next
            fast = fast.next.next
        
        # 核心：从中点切断，形成两个独立的列表
        if pre:
            pre.next = None
        return slow

    def merge(self, list1, list2):
        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 if list1 else list2
        return dummy.next

复杂度分析

• 时间复杂度：$O(N \log N)$，其中 $N$ 为链表的长度。归并排序的分割层数为 $\log N$，每一层合并的总工作量为 $N$。
• 空间复杂度：$O(\log N)$。虽然合并过程不需要额外数组空间，但递归调用的系统栈深度取决于 $\log N$。
  说明：为了逻辑更安全，代码中为 mid_node 函数增加了对 pre 的空值校验。