148. Sort List，148sortlist

148. Sort List，148sortlist

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

代碼如下：

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public ListNode sortList(ListNode head) {
11         if(head==null||head.next==null)
12         return head;
13         
14         ListNode p=head;
15         int count=0;
16         
17         while(p!=null)
18         {
19             count++;
20             p=p.next;
21         }
22         int[]a=new int[count];
23         int c=count;
24         p=head;
25        for(int i=0;i<count;i++)
26        {
27            if(p!=null)
28            a[i]=p.val;
29            p=p.next;
30        }
31        p=head;
32        
33         Arrays.sort(a);
34         for(int i=0;i<c;i++)
35         {
36             p.val=a[i];
37             p=p.next;
38         }
39         return head;
40     }
41 }