Very Concise C++ solution (mergesort one function) only


  • 0
    S

    listOne is the first half of the list.
    listTwo is the second half.
    We sort these two lists first, then merge them.

    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if(!head || !head->next) return head;
            ListNode *listOne = head, *listTwo = head, *fastRunner = head;
            
            while(fastRunner->next && fastRunner->next->next){
                listTwo = listTwo->next;
                fastRunner = fastRunner->next->next;
            }
            
            ListNode *tmp = listTwo->next;
            listTwo->next = nullptr;
            listTwo = tmp;
            
            listOne = sortList(listOne);
            listTwo = sortList(listTwo);
    
            if(listTwo->val < listOne->val) swap(listTwo, listOne);
            head = listOne;
            listOne = listOne->next;
            ListNode *newHead = head;
    
            while(listOne || listTwo){
                if(!listOne) swap(listTwo, listOne);
                else if(listTwo /* && listOne */ && listTwo->val < listOne->val) swap(listOne, listTwo); 
                head->next = listOne;
                listOne = listOne->next;
                head = head->next;
            }
            
            return newHead;
        }
    };
    

Log in to reply
 

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