My c++ code with merge sort


  • 0
    S
    class Solution {
    public:
        void sortP(ListNode * helper,int p){
            ListNode * preFirst=helper;
            ListNode * first=helper->next;
            ListNode * second;
    		ListNode * firstEnd;
            
            while(first){
                int i=0;
                second=first;
    			firstEnd=first;
                while(i<p&&second){
    				if(i<p-1) 
    					firstEnd=firstEnd->next;
                    second=second->next;
                    i++;
                }
                int firstCounter=0,secondCounter=0;
                while(firstCounter<p&&secondCounter<p&&second&&first){
                    if(first->val>second->val){
                        ListNode * node=second->next;
                        second->next=first;
                        preFirst->next=second;
                        preFirst=second;
    					firstEnd->next=node;
                        second=node;
                        secondCounter++;
                    }
                    else if(first->val<second->val){
                        preFirst=first;
                        first=first->next;
                        firstCounter++;
                    }
                    else{
                        ListNode * node=second->next;
                        second->next=first;
                        preFirst->next=second;
                        second=node;
                        preFirst=first;
                        firstEnd->next=node;
                        first=first->next;
                        firstCounter++;
                        secondCounter++;
                    }
                }
                while(firstCounter<p&&first){
                    preFirst=first;
                    first=first->next;
                    firstCounter++;
                }
                while(secondCounter<p&&second){
                    preFirst=second;
                    second=second->next;
                    first=second;
                    secondCounter++;
                }
            }
        }
        
        ListNode* sortList(ListNode* head) {
           int p;
           int i,j,k;
           int n=0;
           ListNode * node=head;
           while(node!=NULL){
               n++;
               node=node->next;
           }
           
           if(n<2) return head;
           ListNode * helper=new ListNode(1);
           helper->next=head;
           for(p=1;p<=n;p+=p){
              sortP(helper,p);
           }
           return helper->next;
           
        }
    };

Log in to reply
 

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