本文共 1376 字，大约阅读时间需要 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/