XingHuiSamaの宝藏之地

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

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

1. 算法核心思想：分治法（Divide and Conquer）

题目对时间复杂度的要求是 O(NlogN)，这在算法中通常指向两种排序：快速排序或归并排序。由于链表不支持随机访问（无法像数组那样通过下标进行 O(1) 的元素交换），归并排序是链表排序的最优解。

归并排序的核心思想是“先拆分，后合并”：

拆分：将长链表从中间物理切断，一分为二，然后对左右两半分别继续拆分，直到链表被拆碎成只包含 1 个节点的微型链表。
合并：由于单个节点天然是有序的，接下来只需将这些微型链表两两合并，最终拼装回一条完整且有序的长链表。

2. 逻辑拆解

递归终止条件（防坠崖）： if (head == NULL || head->next == NULL)。当链表为空或只剩 1 个节点时，无需排序，直接向上一层级返回该节点。这是整个递归能够停止的基石。
找中点与物理断链：利用快慢指针寻找链表中点。为了应对只包含 2 个节点的边界情况（例如 [1, 2]），强制让快指针 fast 提前走一步。这样循环结束时，慢指针 slow 会精准停在左半部分的尾部。随后通过 slow->next = NULL 将原链表物理截断，防止后续操作发生指针越界或死循环。
递归甩锅：将断开的左半边 pre 和右半边 right 再次传入 sortList 函数自身。此时无需关心底层是如何排序的，递归栈会处理好一切，最终返回各自排好序的新头部 lhead 和 rhead。
有序链表合并：调用预先写好的 mergeTwoLists 组件。利用虚拟头节点（Dummy Node）和双指针游标，将 lhead 和 rhead 按照升序规律拉链式地合并成一条新链表，并返回最终结果。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 1. 递归终止条件
        if (head == NULL || head->next == NULL) {
            return head;
        }

        // 2. 快慢指针找中点
        ListNode* pre = head;
        ListNode* fast = pre;
        ListNode* slow = pre;

        fast = fast->next; // 关键：快指针先走一步，防止偶数节点时切不断导致死循环
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            if (fast->next != NULL && fast->next->next != NULL) {
                fast = fast->next->next;
            }
            else {
                fast = fast->next;
            }
        }

        // 3. 断链操作
        ListNode* right = slow->next;
        slow->next = NULL;

        // 4. 分治递归
        ListNode* rhead = sortList(right);
        ListNode* lhead = sortList(pre);

        // 5. 合并有序链表
        return mergeTwoLists(rhead, lhead);
    }

    // 辅助函数：合并两个有序链表
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* pre1 = list1;
        ListNode* pre2 = list2;

        ListNode* result = new ListNode();
        ListNode* ans = result;

        while (pre1 != NULL && pre2 != NULL) {
            if (pre1->val < pre2->val) { // 保持升序
                result->next = pre1;
                pre1 = pre1->next;
                result = result->next;
            }
            else {
                result->next = pre2;
                pre2 = pre2->next;
                result = result->next;
            }
        }

        if (pre1 == NULL) {
            result->next = pre2;
        }
        else {
            result->next = pre1;
        }

        return ans->next;
    }
};

3. 复杂度分析

时间复杂度：O(NlogN)。其中 N 是链表的节点数量。寻找中点需要遍历链表，耗时 O(N)；递归拆分的深度为 logN 层。每一层的合并操作总计耗时也是 O(N)。整体时间复杂度为严格的 O(NlogN)。
空间复杂度：O(logN)。与数组的归并排序需要开辟 O(N) 大小的额外辅助数组不同，链表的合并操作是通过修改指针原地完成的，不需要额外申请节点空间。唯一的空间消耗来自于递归调用时的系统栈深度，即 logN。