1     ListNode *sortList(ListNode *head, int length){
 2         if(length <= 1)
 3             return head;
 4         int l = length/2;
 5         ListNode *tmp = head;
 6         int num = 0;
 7         ListNode *half = NULL;
 8         while(tmp){
 9             num++;
10             if(num == l){
11                 break;
12             }
13             tmp = tmp->next;
14         }
15         half = tmp->next;
16         tmp->next = NULL;
17         ListNode *first = sortList(head, l), *second = sortList(half, length-l);
18         ListNode *result = NULL, *newhead;
19         while(first&&second){
20             if(first->val < second->val){
21                 if(result){
22                     result->next = first;
23                     result = result->next;
24                 }
25                 else{
26                     result = first;
27                     newhead = result;
28                 }
29                 first = first->next;
30             }
31             else{
32                 if(result){
33                     result->next = second;
34                     result = result->next;
35                 }
36                 else{
37                     result = second;
38                     newhead = result;
39                 }
40                 second = second->next;
41             }
42         }
43         if(first)
44             result->next = first;
45         if(second)
46             result->next = second;
47         return newhead;
48     }
49     ListNode *sortList(ListNode *head) {
50         // IMPORTANT: Please reset any member data you declared, as
51         // the same Solution instance will be reused for each test case.
52         if(head == NULL || head->next == NULL)
53             return head;
54         int length = 0;
55         ListNode *tmp = head;
56         while(head){
57             length++;
58             head = head->next;
59         }
60         return sortList(tmp, length);
61     }