C++ Solution using quicksort


  • 0
    X
    class Solution {
    private:
        //return last node
        ListNode* sortPart(ListNode* first){
            if(first->next==NULL)return first;
            if(first->next->next==NULL)return first->next;
            ListNode* last=first,*pa=first->next,*pa2=pa,*tail=pa,*tmp=NULL;
            int p=pa->val;
            bool flag=true;
            //partition using pa
            while(tail->next){
                tmp=tail->next;
                int t=tmp->val;
                if(t<p){
                    last->next=tmp;
                    last=last->next;
                    tail->next=tmp->next;
                }else{
                    //I use pa2 to record the end of the list part begin from pa, where the node's val = pa->val.We don't need to sort this part.
                    // Actually, I made this operation because my code runs extremely slow(about 1000ms) when the input is a large array consists of 1,2,3. the partition can always be imbalance.  It's not a very clean  approach, and consequently, my total runtime is 56ms, not good.
                    if(t!=p)flag=false;
                    if(flag)pa2=tail;
                    tail=tail->next;
                }
            }
            last->next=NULL;
            //part1:from first to last
            last=sortPart(first);
            last->next=pa;
            //part2:from pa2 to tail
            last=sortPart(pa2);
            return last;
        }
    public:
        ListNode* sortList(ListNode* head) {
            ListNode* first=new ListNode(0);
            first->next=head;
            ListNode* tail=sortPart(first);
            tail->next=NULL;
            return first->next;
        }
    };

  • 0
    Q

    @xiongjzh well, anything that uses recursive call is wrong, because it will be using O(n log n) stack space.


Log in to reply
 

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