public class sortList_148 {
    // sortList：主函数，用于递归排序链表
    public ListNode sortList(ListNode head) {
        // 递归终止条件：如果链表为空或者只有一个节点，说明已经有序，直接返回
        if (head == null || head.next == null) {
            return head;
        }

        // 定义双指针（快慢指针）用于寻找中点
        // slow：慢指针，每次走一步，最终指向中间节点（作为左半部分的尾节点）
        ListNode slow = head;
        // fast：快指针，每次走两步，用于辅助判断是否到达末尾，并配合 slow 寻找中点
        ListNode fast = head.next;

        // 定位中点：当快指针走到尾节点或其下一个节点为空时，slow 正好停在链表中点
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // mid：记录右半部分链表的头节点（即中点之后的部分）
        ListNode mid = slow.next;
        // 将左半部分链表截断，使 slow.next 指向 null
        slow.next = null;
        
        // left：递归排序左半部分链表，返回排序后左半部分的头节点
        ListNode left = sortList(head);
        // right：递归排序右半部分链表，返回排序后右半部分的头节点
        ListNode right = sortList(mid);
        
        // 将两个已排序的子链表合并，并返回最终的排序结果
        return merge(left, right);
    }

    // merge：合并两个有序链表
    public ListNode merge(ListNode left, ListNode right) {
        // start：创建虚拟头节点（哑节点），用于统一处理合并时的边界情况，它的 next 将指向结果链表的头部
        ListNode start = new ListNode(0);
        // copy：工作指针，初始指向虚拟头节点，用于串联合并后的节点
        ListNode copy = start;

        // 遍历：当左右两个链表都有节点时，进行逐个比较并拼接
        while (left != null && right != null) {
            // 比较当前两个节点的值，将较小的节点接到 copy 后面
            if (left.val <= right.val) {
                copy.next = left;
                left = left.next; // 将左链表的指针向后移动
            } else {
                copy.next = right;
                right = right.next; // 将右链表的指针向后移动
            }
            // 合并一个节点后，copy 指针向后移动，指向新链表的末尾
            copy = copy.next;
        }

        // 如果左链表还有剩余节点，直接将剩余部分接在 copy 后面
        if (left != null) {
            copy.next = left;
        }

        // 如果右链表还有剩余节点，直接将剩余部分接在 copy 后面
        if (right != null) {
            copy.next = right;
        }

        // 返回虚拟头节点的下一个节点，即真正的合并后链表头节点
        return start.next;
    }
}