147. Insertion Sort List

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 };