148. 排序链表

链表"/>

148. 排序链表

给你链表的头结点 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;}//有一个是空退出 或者都是空 退出whileres.next=(left==null?right:left);return dummy.next;    }
}