力扣———对链表的插入排序（画图详解）

题目：

对链表进行插入排序
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序。
每次迭代时，从输入数据中移除一个元素，并原地将其插入到已排好序的链表中。（转载力扣）

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

示例1：

输入: 4->2->1->3
输出: 1->2->3->4

示例2

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

分析

先把链表分成两个部分:把第一个数，与后面的数分开，然后在把后面的数一个一个与前面进行进行对比，在插入进去

首先我们需要先对第二个链表定义两个指针:cur，next（cur是指向的值是跟前面的链表进行对比），next是cur的下一个值
对第一个链表定义两个指针，head，c,p,head是第一个链表的头节点，c是要跟第二个链表进行比较的当前的值，p是c前一个值。

头插，也就是p为null时,cur<c,插入完之后在把cur赋值给head

插在中间，p不等于null却cur<c

c循环结束后，进行尾插：

struct ListNode* insertionSortList(struct ListNode* head){
    //先判断head是否为NULL
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    //先定义cur
   struct   ListNode* cur=head->next;
    head->next=NULL;//将两个链表断开
    while(cur)//当cur为空时，则循环结束
    {
         struct ListNode* c=head;//定义第一链表的c,和p
      struct  ListNode* p=NULL;
      struct  ListNode*  next=cur->next;//定义第二个链表的下一个节点
        while(c)//第二个循环
        {
            if(cur->val<c->val)//当找到cur比c小，跳出来
            {
                break;
            }
            else//找不到继续找
            {
                p=c;
                c=c->next;
            }
        }
        if(p==NULL)//一种是插在最前面
        {
            cur->next=c;
            head=cur;
        }
        else//另外一种是尾插，或者插在中间
        {
            p->next=cur;
            cur->next=c;
        }
        cur=next;//最后cur在走一步

    }
    return head;
}