给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
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;
}
}
