输入：head = [4,2,1,3]
输出：[1,2,3,4]

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

输入：head = []
输出：[]

class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head); // 开始对链表进行归并排序
    }
    
    /**
     * 对给定的链表进行归并排序
    */
    ListNode mergeSort(ListNode head){
        if(head == null || head.next == null){
            return head; // 如果链表为空或只有一个节点，无需排序直接返回
        }
        
        // 获取链表的中间节点，分别对左右子链表进行排序
        ListNode mid = getMid(head); // 使用快慢指针找到链表的中点
        ListNode rightHead = mid.next; // 右半部分链表的头节点
        mid.next = null; // 断开链表，分为两部分
        ListNode leftSorted = mergeSort(head); // 对左半部分进行归并排序
        ListNode rightSorted = mergeSort(rightHead); // 对右半部分进行归并排序
        return mergeTwoLists(leftSorted, rightSorted); // 合并两个已排序的链表
    }

    /**
     * 获取以head为头节点的链表中间节点
     * 如果链表长度为奇数，返回最中间的那个节点
     * 如果链表长度为偶数，返回中间靠左的那个节点
    */
    ListNode getMid(ListNode head){
        ListNode slow = head, fast = head.next; // 快慢指针，fast比slow快一步
        while(fast != null && fast.next != null) {
            slow = slow.next; // 慢指针每次前进一步
            fast = fast.next.next; // 快指针每次前进两步
        }
        return slow; // 当快指针到达链表尾部时，慢指针指向中间节点
    }

    /**
     * 合并两个有序链表 list1 和 list2
    */
    ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(); // 创建一个伪头节点，便于处理链表头部
        ListNode tail = dummy; // 尾指针，用于构建新链表

        while(list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1; // 将list1的当前节点连接到新链表
                list1 = list1.next; // list1向前移动
            } else {
                tail.next = list2; // 将list2的当前节点连接到新链表
                list2 = list2.next; // list2向前移动
            }
            tail = tail.next; // 移动尾指针
        }

        tail.next = (list1 != null) ? list1 : list2; // 将剩余的部分连接到新链表
        return dummy.next; // 返回新链表的头节点，即伪头节点的下一个节点
    }
}