Sort a linked list using insertion sort.
分析
使用插入排序，排序一个链表。
先列出首节点，然后依次对比节点大小，然后插入到合适的位置即可。
C代码如下，已通过。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* insertionSortList(struct ListNode* head) {
if(head==NULL)return NULL;
struct ListNode * ans=head,*p1,*p2,*p3,*p4;
p1=head->next;
ans->next=NULL;
while(p1!=NULL)
{
p2=p1->next;
p3=ans;
p4=p3;
while(p3!=NULL&&p3->val <= p1->val)
{
p4=p3;
p3=p3->next;
}
if(p3==ans)
{
ans=p1;
p1->next=p3;
}
else if(p3==NULL)
{
p4->next=p1;
p1->next=NULL;
}
else
{
p4->next=p1;
p1->next=p3;
}
p1=p2;
}
return ans;
}
