题目链接：https://leetcode-cn.com/problems/insertion-sort-list/

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

示例 1：

输入: 4->2->1->3
输出: 1->2->3->4
示例 2：

输入: -1->5->3->4->0
输出: -1->0->3->4->5

 1 struct ListNode* insertionSortList(struct ListNode* head){
 2     if(head==NULL||head->next==NULL) return head;
 3     struct ListNode* L=(struct ListNode*)malloc(sizeof(struct ListNode));
 4     L->next=head;
 5     struct ListNode *p=head->next,*pre,*tmp,*rear;
 6     rear=head;
 7     head->next=NULL;
 8     while(p){
 9         tmp=p->next;
10         if(p->val>rear->val){
11             rear->next=p;
12             rear=p;
13             rear->next=NULL;
14             p=tmp;
15         }else{
16             pre=L;
17             while(pre->next&&pre->next->val<p->val){
18                 pre=pre->next;
19             }
20             p->next=pre->next;
21             pre->next=p;
22             p=tmp;
23         }
24     }
25     return L->next;
26 }