My 30line 55ms O(nlogn) C++ solution use constant space without recurse, defeat 99.58%


  • 0
    M
    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if(!head)return NULL;
            ListNode *dummy=new ListNode(0),*p,*q,*node=head;
            dummy->next=head;
            int unit=1,countp,countq,len=1;
            while(node=node->next)len++;
            while(unit<len){
                q=p=dummy;
                while(p->next){
                    for(int i=0;i<unit&&q->next;i++)q=q->next;
                    if(!q->next)break;
                    countp=countq=0;
                    while(countp<unit||countq<unit){
                        if(countp==unit){countq++;q=q->next;}
                        else if(countq<unit&&q->next->val<p->next->val){
                            node=q->next;
                            q->next=node->next;
                            node->next=p->next;
                            p->next=node;
                            countq++;
                        }else countp++;
                        p=p->next;
                        if(!q->next)countq=unit;
                    }
                }
                unit<<=1;
            }
            return dummy->next;
        }
    };

Log in to reply
 

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