148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

利用mergesort

merge 操作只能合并2个有序的子序列

所以利用递归对每个子序列进行排序，排序后merge。

 1 class Solution {
 2     public ListNode sortList(ListNode head) {
 3         if(head==null || head.next==null) return head;
 4         
 5         //1 split 
 6         ListNode pre=null,slower =head,faster=head;
 7         while(faster!=null && faster.next!= null){
 8             pre = slower;
 9             slower = slower.next;
10             faster = faster.next.next;
11         }
12         pre.next = null;
13         //2 sort 
14         ListNode l1 = sortList(head);
15         ListNode l2 = sortList(slower);
16         //3 merge
17         return Merge(l1,l2);
18         
19     }
20     
21     public ListNode Merge(ListNode l1,ListNode l2){
22         ListNode l ,p;
23         l = new ListNode(0);
24         p=l;
25         
26         while(l1 != null&& l2 != null){
27             if(l1.val<l2.val){
28                 p.next = l1;
29                 l1 = l1.next;
30             }
31             else{
32                 p.next = l2;
33                 l2 = l2.next;
34             }
35             p = p.next;
36         }
37         if(l1==null) p.next = l2;
38         if(l2==null) p.next = l1;
39         return l.next;
40     }
41 }