148. 排序链表

class Solution {
    public ListNode sortList(ListNode head) {
        /**
        分治法求解 即可
         */
         if(head==null||head.next==null){ return head;}
         ListNode low=head;
         ListNode fast=head.next;
         //快慢指针找 中点
         while(fast!=null&&fast.next!=null){
             fast=fast.next.next;
             low=low.next;
         }
         //low是中点
         ListNode rightNode=low.next;//右边的节点起点
         low.next=null;
         ListNode left=sortList(head);
         ListNode right=sortList(rightNode);
         return merge(left,right);
         
    }
    //合并
    public ListNode merge(ListNode left,ListNode right){
        ListNode dummy=new ListNode(-1);
        ListNode res=dummy;
        while(left!=null&&right!=null){
            if(left.val<right.val){
                res.next=left;
                left=left.next;
            }else{
                res.next=right;
                right=right.next;
            }
           res=res.next;
        }
        //有一个是空退出 或者都是空 退出while
        res.next=(left==null?right:left);
        return dummy.next;    
    }
}