struct ListNode* insertionSortList(struct ListNode* head){
//特殊情况讨论
if(head == NULL || head->next == NULL)
{
return head;
}
//1、初始条件
struct ListNode* sortHead = head;
struct ListNode* cur = head->next;
sortHead->next = NULL;
while(cur)//2、终止条件
{
struct ListNode* next = cur->next;
//比较cur元素和sortHead里面元素的大小，从前往后比；
struct ListNode* p = NULL, *c = sortHead;
while(c)
{
if(cur->val < c->val)
break;
p = c;
c = c->next;
}
//这里跳出循环，要么是找到cur比一个c小，要么是c遍历完，cur是最大的数；
//下面把cur插到p的后面（p的作用在这）
//但是需要考虑cur比第一个元素小的情况，也就是p为NULL
if(p == NULL)
{
cur->next = sortHead;
sortHead = cur;
}
else
{
p->next = cur;
cur->next = c;
}
cur = next;
}
return sortHead;
}
ps:思路
