[LintCode] 链表插入排序

 1 /**
 2  * Definition of ListNode
 3  * class ListNode {
 4  * public:
 5  *     int val;
 6  *     ListNode *next;
 7  *     ListNode(int val) {
 8  *         this->val = val;
 9  *         this->next = NULL;
10  *     }
11  * }
12  */
13 class Solution {
14 public:
15     /**
16      * @param head: The first node of linked list.
17      * @return: The head of linked list.
18      */
19     ListNode *insertionSortList(ListNode *head) {
20         // write your code here
21         ListNode* new_head = new ListNode(0);
22         new_head -> next = head;
23         ListNode* pre = new_head;
24         ListNode* cur = head;
25         while (cur) {
26             if (cur -> next && cur -> next -> val < cur -> val) {
27                 while (pre -> next && pre -> next -> val < cur -> next -> val)
28                     pre = pre -> next;
29                 /* Insert cur -> next after pre. */
30                 ListNode* temp = pre -> next;
31                 pre -> next = cur -> next;
32                 cur -> next = cur -> next -> next;
33                 pre -> next -> next = temp;
34                 /* Move pre back to the starting node. */
35                 pre = new_head;
36             }
37             else cur = cur -> next;
38         }
39         ListNode* res = new_head -> next;
40         delete new_head;
41         return res;
42     }
43 };