Insertion Sort List

用户1624346

发布于 2018-04-17 16:33:33

5780

发布于 2018-04-17 16:33:33

文章被收录于专栏：calmound

家里网实在太烂了，弄得我都不想上网，每次打开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;

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2014-07-30 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法