My c++ quick sort solution, any comments?


  • 0
    T
    ListNode *sortList(ListNode *head) {
            if(!head) return head;
            ListNode *tail=NULL;
            head=sortList2(head,tail);
            return head;
        }
        
        ListNode *sortList2(ListNode *head, ListNode *&tail) {
            ListNode *rethead=head;
            ListNode *node=head;
            if (!(node->next)) {
                tail=head;
                return head;
            }
            ListNode *head1=NULL,*tail1=NULL;
            ListNode *head2=NULL,*tail2=NULL;
            ListNode *head3=NULL,*tail3=NULL;
            // read first value as binary sort
            int value=head->val;
            while(node){
                if (node->val<value) {
                    if(!head1) {
                        head1=node;
                        tail1=node;
                    } else {
                        tail1->next=node;
                        tail1=node;
                    }
                } else if(node->val==value) {
                    if(!head2) {
                        head2=node;
                        tail2=node;
                    } else {
                        tail2->next=node;
                        tail2=node;
                    }
                } else {
                    if(!head3) {
                        head3=node;
                        tail3=node;
                    } else {
                        tail3->next=node;
                        tail3=node;
                    }
                }
                node=node->next;
            }
            if(tail1) tail1->next=NULL;
            if(tail2) tail2->next=NULL;
            if(tail3) tail3->next=NULL;
            
            if(head1) head1=sortList2(head1,tail1);
            if(head3) head3=sortList2(head3,tail3);
            
            // form the whole list
            if(tail1) {
                tail1->next=head2;
                if(tail2) tail2->next=head3;
                if(head3) {
                    tail=tail3;
                } else {
                    tail=tail2;
                }
                return head1;
            } else {
                if(tail2) tail2->next=head3;
                if(head3) {
                    tail=tail3;
                } else {
                    tail=tail2;
                }
                return head2;
            }
            
        }

Log in to reply
 

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