本文共 1384 字，大约阅读时间需要 4 分钟。

链表中的插入排序

typedef struct ListNode ListNode;struct ListNode* insertionSortList(struct ListNode* head){
       if(head==NULL||head->next==NULL)    return head;    //新链表头节点为sorthead    ListNode* sorthead=head;    ListNode* cur=head->next;    sorthead->next=NULL;    while(cur)    {
           ListNode* post=cur->next;                //如果cur的val小于sorthead的val;将cur头插在sorthead前        if(cur->val<=sorthead->val)        {
               cur->next=sorthead;            sorthead=cur;        }        //cur的val大于sorthead的val，中间插入与尾插        else        {
               ListNode* sortPrev=sorthead;            ListNode* sortNext=sortPrev->next;            while(sortNext)            {
                   //cur的val大于等于sortPrev的val，cur插入sortprev后sortNext后                if(sortNext->val>=cur->val)                {
                       sortPrev->next=cur;                    cur->next=sortNext;                    break;                }                //不符合cur的插入位置，sortPrev与sortNext同时往后走；                else                {
                       sortPrev=sortNext;                    sortNext=sortNext->next;                }            }            //如果sortNext走到NULL位，则尾插            if(sortNext==NULL)            {
                   sortPrev->next=cur;                cur->next=NULL;            }        }        //cur迭代向后走；        cur=post;    }    return sorthead;}

转载地址：http://wmzaz.baihongyu.com/