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 = []
输出：[]

提示：

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

**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

归并排序（递归法），先分再合

class Solution {
    public ListNode sortList(ListNode head) {
        // 如果链表为空或只有一个元素，则不需要排序，直接返回
        if (head == null || head.next == null)
            return head;
        
        // 使用快慢指针法找到链表的中间节点。
        // 注意，fast初始值为head.next而不是head！
        // 这样可以确保在链表长度为偶数时，循环结束时slow指向的是中间两个节点中的第一个。
        // 如果还不懂，请看下面的例子。
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; // 慢指针每次移动一步
            fast = fast.next.next; // 快指针每次移动两步
        }
        // 此时slow指向中间节点或两个中间节点的第一个

        // 将链表从中间分为两部分
        ListNode rightHead = slow.next; // 右半部分的起始节点
        slow.next = null; // 切断链表

        // 对左半部分进行递归排序
        ListNode left = sortList(head);
        // 对右半部分进行递归排序
        ListNode right = sortList(rightHead);

        // 合并两个已排序的链表
        ListNode dummy = new ListNode(0); // 新建一个虚拟节点
        ListNode h = dummy; // 新建一个构造节点
        // 遍历两个链表，按顺序重组节点。
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left; // 将较小节点链接到结果链表
                left = left.next; // 移动左侧链表指针
            } else {
                h.next = right; // 将较小节点链接到结果链表
                right = right.next; // 移动右侧链表指针
            }
            h = h.next; // 移动结果链表指针
        }
        // 将未结束的链表部分连接到结果链表后面
        h.next = left != null ? left : right;
        // 返回排好序的链表的头节点
        return dummy.next;
    }
}

• 时间复杂度：O(nlog n)，其中 n 是链表的长度。
• 空间复杂度：O(log n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间。

例子：

假设链表是 1 -> 2 -> 3 -> 4 -> null，我们希望找到中间节点：

- 如果 `fast` 从 `head` 开始：
    - 第一次循环：`slow = 1`, `fast = 1`。
    - 第二次循环：`slow = 2`, `fast = 3`。
    - 第三次循环：`slow = 3`, `fast = null`，此时快指针到了链表末尾后的 `null`，循环结束，慢指针指向 `3`，不好。

- 如果 `fast` 从 `head.next` 开始：
    - 第一次循环：`slow = 1`, `fast = 2`。
    - 第二次循环：`slow = 2`, `fast = 4`。此时快指针到了链表末尾，循环结束，慢指针指向 `2`，好。