// @Title: 排序链表 (Sort List)
// @Author: qisiii
// @Date: 2024-06-13 17:52:58
// @Runtime: 9 ms
// @Memory: 55.4 MB
// @comment: 
// @flag: 
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
    if(head==null||head.next==null){
            return head;
        }
        ListNode slow=head;
        ListNode fast=head;
        ListNode pre=head,l=pre;
        while(fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;
        ListNode left=sortList(l);
        ListNode right=sortList(slow);
        ListNode cur=new ListNode(-1),result=cur;
        //进行合并
        while(left!=null&&right!=null){
            if(left.val>right.val){
                cur.next=right;
                right=right.next;
            }else{
                cur.next=left;
                left=left.next;
            }
            cur=cur.next;
        }
        cur.next=left==null?right:left;
        return result.next;
    }
}