/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* &head) {//改为引用,降低内存,虽然也降低不了多少
if(head==NULL||head->next==NULL)
return head;
ListNode *daicharu=head->next,*tail,*p=head,*pre=NULL,*temp=NULL;
while(p&&daicharu&&p->val<=daicharu->val)
{//第一个优化,初始化待插入的节点开始位置
p=p->next;
daicharu=daicharu->next;
}
tail=p;
p->next=NULL;
while(daicharu)
{
p=head;
pre=NULL;//p的前节点,开始为首节点的前一个节点NULL
temp=daicharu;
daicharu=daicharu->next;
if(temp->val>=tail->val)
{//第二个优化,大于尾节点,直接接上就可以了
tail->next=temp;
tail=temp;
tail->next=NULL;
continue;//插入下一个元素
}
//否则从头开始找位置
while(p&&temp->val>=p->val){
pre=p;
p=p->next;
}
if(pre!=NULL)
{//插在最前面
pre->next=temp;
temp->next=p;
pre=pre->next;
}else
{//普通情况
temp->next=p;
pre=temp;
head=pre;
}
}
return head;
}
};
原文链接: https://www.cnblogs.com/lxzbky/p/14015922.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/399955
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!