C++ 49ms quicksort


  • 0

    Inspired by quicksort:
    int q = partition(A, p, r);
    quicksort(A, p, q - 1);
    quicksort(A, q + 1, r);

        //Same idea as partition(int* A, int p, int r) in Quicksort. Return new head.
        ListNode* partition(ListNode* head,ListNode* pivot){
            ListNode* pre,*cur,*next,*tailhead;
            pre=new ListNode(0);
            ListNode* Head=pre;
            pre->next=head;
            cur=head;
            next=cur->next;
            tailhead=pivot;
            while(cur!=pivot){
                if(cur->val>pivot->val){
                    pre->next=next;
                    cur->next=NULL;
                    tailhead->next=cur;
                    
                    tailhead=cur;
                    cur=next;
                    if(next) next=next->next;
                }else{
                    pre=pre->next;
                    cur=cur->next;
                    if(next) next=next->next;
                }
            }
            return Head->next;
        }
        
        
        ListNode* sortList(ListNode* head) {
            if(!head||!head->next) return head;
            ListNode* pivot=head->next; 
            while(pivot->next) pivot=pivot->next; 
            ListNode* headhead=partition(head,pivot); //Use tail as pivot to patition the linked list.
            ListNode* res=headhead; //Store the new head.
            while(headhead)
                if(!headhead->next||headhead->val<=headhead->next->val) headhead=headhead->next;
                else break;
            if(!headhead) return res; //If headhead is NULL, then list is sorted, simply return new head.
            else{
                //We have 2 partially sorted list divided by pivot, like h->...->pivot->t->...->tail.
                //Just divide them, sort each part recursively, and link them.
                ListNode* newtail=pivot->next;
                pivot->next=NULL;
                ListNode* pre=res;
                if(pre!=pivot) while(pre->next!=pivot) pre=pre->next;
                pre->next=NULL;
                
                ListNode* h=sortList(res);
                ListNode* t=sortList(newtail);
                ListNode* temp=h;
                while(temp->next) temp=temp->next;
                temp->next=pivot;
                pivot->next=t;
                return h;
            }
        }
    

Log in to reply
 

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