首页 > 代码库 > Insertion Sort List
Insertion Sort List
家里网实在太烂了，弄得我都不想上网，每次打开oj特别慢，提交题目等刷出来更慢。对于这题感觉脑子不好用啊，写的好繁琐。不过所幸最终脑子还是转过乐弯。。。就是指针next的交换，对于当前遍历的ret点，判断前面是否可以插入，若可以插入，则插入点的前一点指向ret，ret指向插入点的后一点，
然后再将前面已经排好序的链表的最后一个节点，指向ret的下一个节点。
注意要有个临时变量记录ret指针，在弄临时变量的next来遍历下一个要插入的节点，不然ret一旦插入后，其next就发生变化了。
class Solution{public: ListNode *insertionSortList(ListNode *head) { if(!head) return head; if(!head->next) return head; ListNode *sor,*ret; sor = new ListNode(-9999999); sor->next=head; ret=head->next; ListNode *pre1,*thi1; ListNode *pre2,*thi2; pre1=head; pre2=head; while(ret) { ListNode *tmp=ret; thi2=ret; pre1=sor; thi1=sor->next; while(thi1->val<ret->val && thi1!=ret) { thi1=thi1->next; pre1=pre1->next; } ret=thi2->next; if(thi1!=thi2) { pre2->next=thi2->next; pre1->next=thi2; thi2->next=thi1; } else pre2=tmp; } head=sor->next; delete sor; return head; }} t;
方法二：参考的别人
建立一个helper头结点，然后依次将head链表中的结点有序的插入到helper链表中
class Solution{public: ListNode *insertionSortList(ListNode *head) { if(head==NULL || head->next==NULL) return head; ListNode *cur=head; ListNode *helper=new ListNode(0); ListNode *pre; while(cur) { ListNode *next=cur->next; pre=helper; while(pre->next!=NULL && pre->next->val<cur->val) { pre=pre->next; } cur->next=pre->next; pre->next=cur; cur=next; } return helper->next; }} t;
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。