147. Insertion Sort List，147insertion

147. Insertion Sort List，147insertion

Sort a linked list using insertion sort.

用一個輔助指針來做表頭避免處理改變head的時候的邊界情況。

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* insertionSortList(ListNode* head) {
12       if(head == NULL){
13           return head;
14       }
15       
16       ListNode* helper = new ListNode(0);
17       ListNode* pre = helper;
18       ListNode* cur = head;
19       
20       while(cur != NULL){
21           ListNode* next = cur->next;
22           //保存head位置
23           pre = helper;
24           while(pre->next != NULL && pre->next->val < cur->val){
25               pre = pre->next;
26           }
27           //插入
28           cur->next = pre->next;
29           pre->next = cur;
30           //恢復
31           
32           cur = next;
33       }
34       return helper->next;
35     }
36 };