1 /**
 2  * Definition for singly-linked list.
 3  * class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12 public class Solution {
13     public ListNode sortList(ListNode head) {
14         if(head==null||head.next==null)
15             return head;
16         ListNode fast=head;
17         ListNode slow=head;
18         while(fast.next!=null&&fast.next.next!=null){
19             fast=fast.next.next;
20             slow=slow.next;
21         }
22         fast=slow.next;
23         slow.next=null;
24         slow=sortList(head);
25         fast=sortList(fast);
26         return merge(slow,fast);
27     }
28 
29     private ListNode merge(ListNode slow, ListNode fast) {
30         // TODO Auto-generated method stub
31         ListNode head=new ListNode(0);
32         ListNode cur=head;
33         while(slow!=null&&fast!=null){
34             if(slow.val<fast.val){
35                 cur.next=slow;
36                 slow=slow.next;
37             }else{
38                 cur.next=fast;
39                 fast=fast.next;
40             }
41             cur=cur.next;
42         }
43         if(slow!=null){
44             cur.next=slow;
45         }
46         if(fast!=null){
47             cur.next=fast;
48         }
49         return head.next;
50     }
51 }