Insertion Sort List

Sort a linked list using insertion sort.

代码：

 1     ListNode *insertionSortList(ListNode *head) {
 2         // IMPORTANT: Please reset any member data you declared, as
 3         // the same Solution instance will be reused for each test case.
 4         if(!head)
 5             return NULL;
 6         ListNode *start = head, *end = head, *tmp = head->next, *pre, *next, *cur;
 7         while(tmp){
 8             next = tmp->next;
 9             pre = NULL;
10             cur = start;
11             end->next = NULL;
12             while(cur){
13                 if(cur->val > tmp->val){
14                     if(!pre){
15                         start = tmp;
16                         tmp->next = cur;
17                     }
18                     else{
19                         pre->next = tmp;
20                         tmp->next = cur;
21                     }
22                     break;
23                 }
24                 if(!pre)
25                     pre = cur;
26                 else
27                     pre = pre->next;
28                 cur = cur->next;
29             }
30             if(!cur){
31                 pre->next = tmp;
32                 tmp->next = NULL;
33                 end = tmp;
34             }
35             tmp = next;
36         }        
37         return start;
38     }

第二遍

 1     ListNode *insertionSortList(ListNode *head) {
 2         // IMPORTANT: Please reset any member data you declared, as
 3         // the same Solution instance will be reused for each test case.
 4         if(!head)
 5             return NULL;
 6         ListNode *result, *tmp, *pretmp, *cur, *next;
 7         cur = head->next;
 8         result = head;
 9         result->next = NULL;
10         while(cur){
11             tmp = result;
12             next = cur->next;
13             while(tmp){
14                 if(tmp->val > cur->val)
15                     break;
16                 pretmp = tmp;
17                 tmp = tmp->next;
18             }
19             if(tmp == result){
20                 cur->next = result;
21                 result = cur;
22             }
23             else{
24                 pretmp->next = cur;
25                 cur->next = tmp;
26             }
27             cur = next;
28         }
29         return result;
30     }