Relatively simple code


  • 0
    F
    //b1...e1   b2...e2
    ListNode * sort(ListNode * b, ListNode* e){
        if(b==e) return b;
        ListNode * b1=b, *e1=b, *b2=b, *e2=e;
        //Find the e1, b2
        for(ListNode *fast=b; fast->next!=e;){
            e1=e1->next;
            fast=fast->next;
            if(fast->next!=e) fast=fast->next;
        }
        b2=e1->next;
        e1->next=nullptr;
        //sort the two sublists individually.
        b1=sort(b1, e1);
        b2=sort(b2, e2);
        //then sort the two sublists together
        ListNode * dummy=new ListNode(0);
        ListNode *d=dummy;
        while( b1!=nullptr && b2!=nullptr){
            if((b1->val)<(b2->val)){
                d->next=b1;
                b1=b1->next;
            }
            else{
                d->next=b2;
                b2=b2->next;
            }
            d=d->next;
        }
        if(b1==nullptr) d->next=b2;
        else d->next=b1;
        //delete dummy 
        b=dummy->next;
        delete dummy;
        return b;
    }
    
    ListNode *sortList(ListNode *head) {
        if(head==0 || head->next==0) return head;
        ListNode * last=head;
        while(last->next!=nullptr){
            last=last->next;
        }
        return sort(head,last);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.