Leetcode刷题——对链表进行插入排序

 题解：（想说的都在注释里）

struct ListNode* insertionSortList(struct ListNode* head){
    if(head==NULL || head->next == NULL)
    {
        return head;//如果为空或者只有一个节点，则不需要排序
    }

    //   1、初始条件
    struct ListNode* sortHead = head;//设置一个节点记录第一个节点
    struct ListNode* cur = head->next;//设置一个cur连接原原头结点的下一节点
    sortHead->next = NULL;//将第一第二个节点断开，成为两部分

    while(cur)  // 2、终止条件
    {
        //3、迭代条件
        struct ListNode* next = cur->next;

        //将cur节点插入前面的有序区间
        struct ListNode* p = NULL, *c = sortHead;//用p记录前一节点，c记录当前位置
        while(c)
        {
            if(cur->val < c->val) //插入值小于当前节点值，则开始插入
            {
                
                break;   //将插入节点为最大值节点（用尾插）与正常情况结合处理
            }
            else      //如果比较大于，则移动前后指针
            {
                p = c;
                c = c->next;
            }
        }

        //可获得三种节点地址 
        //1、NULL说明 插入节点值最小（用头插）
        //2、节点c非空 说明插入值在链表中间
        //3、节点c为空 说明插入节点值最大（用尾插）

        if(p == NULL)//如果前驱节点为空，则用头插
        {
            cur->next = c;
            sortHead = cur;
        }
        else //二三情况结合处理
        {
            p->next = cur; 
            cur->next = c;     
        }
        
        //迭代cur当前节点
        cur = next;
    }

    return sortHead;

}