MergeSort, C++, beats 94%, O(1) Space


  • 0
    class Solution {
    public:
        ListNode* getNthFollower(ListNode *start, size_t step){
            ListNode* iter = start;
            for(int i=0; i<step && iter; i++){
                iter = iter->next;
            }
    
            return iter;
        }
    
        ListNode* sortList(ListNode* head) {
    
            int length = 0;
            ListNode* iter = head;
            while(iter){
                length ++;
                iter = iter->next;
            }
    
    
            int skip = 2;
            while(skip<length*2){
                ListNode* sortedList1 = head;
                ListNode* sortedList2 = getNthFollower(head, skip/2);
                ListNode* end = getNthFollower(head, skip);
                ListNode* sortedList1Pre = NULL;
    
                while(sortedList2){
    
                    ListNode* iter1 = sortedList1;
                    ListNode* iter2 = sortedList2;
    
                    ListNode *h, *t;
                    if(iter1->val > iter2->val){
                        h = t = iter2;
                        iter2 = iter2->next;
                    }else{
                        h = t = iter1;
                        iter1 = iter1->next;
                    }
    
                    while(iter1 != sortedList2 && iter2!=end){
                        if(iter1->val > iter2->val){
                            t = t->next = iter2;
                            iter2 = iter2->next;
                        }else{
                            t = t->next = iter1;
                            iter1 = iter1->next;
                        }
                    }
    
                    if(iter1 == sortedList2){
                        t = t->next = iter2;
                    }else{
                        t = t->next = iter1;
                        while(t->next !=sortedList2 ){
                            t = t->next;
                        }
                        t->next = end;
                    }
    
                    if(sortedList1 == head){
                        head = h;
                    }else{
                        sortedList1Pre->next = h;
                    }
                    sortedList1Pre = getNthFollower(h, skip-1);
                    sortedList1 = end;
                    sortedList2 = getNthFollower(end, skip/2);
                    end = getNthFollower(end, skip);
                }
    
    
                skip <<= 1;
            }
    
            return head;
        }
    };
    

  • 0
    P

    Zhen Ji Zhi !


Log in to reply
 

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