insertion-sort-list 插入法排序链表

 1 /**
 2  * struct ListNode {
 3  *  int val;
 4  *  struct ListNode *next;
 5  * };
 6  */
 7  
 8 class Solution {
 9 public:
10     /**
11      *
12      * @param head ListNode类
13      * @return ListNode类
14      */
15     ListNode* insertionSortList(ListNode* head) {
16         if(head == NULL) return head;
17         ListNode* dumy = new ListNode(INT_MIN);
18         ListNode* cur = head;
19         ListNode* pre = dumy;
20         while(cur != NULL){
21             pre = dumy; //从新链表的头节点开始查找插入位置
22             while(pre->next != NULL && cur->val > pre->next->val)
23                 pre = pre->next;
24             ListNode* next = cur->next; //记录后继结点
25             cur->next = pre->next; //插入
26             pre->next = cur;
27             cur = next;
28         }
29         return dumy->next;
30     }
31 };