My recursive and iterative versions C++ (60ms)


  • 0
    D

    Both are based on divide-and-conquer. divide the list into two, sort each of them and merge. Below is the recursive version. Due to the recursion, it needs O(logN) space, not constant.

    class Solution {
    private:
        ListNode *split(ListNode *head) //split the list into two
        {
            ListNode *fast, *slow;
            fast=slow=head;
            while(fast->next && fast->next->next)
            {
                fast = fast->next->next;
                slow = slow->next;
            }
            fast = slow->next;
            slow->next = nullptr;
            return fast;
        }
        ListNode *merge(ListNode *head1, ListNode*head2) // merge two sorted lists
        {
            ListNode dummy(0);
            dummy.next = head1;
            head1 = &dummy;
            
            while(head2)
            {
                if(head1->next && head1->next->val <= head2->val) head1 =head1->next;
                else swap(head1->next, head2);
            }
            return dummy.next;
        }
        
    public:
        ListNode* sortList(ListNode* head) {
            if(!head || !head->next) return head;
            ListNode* newHead = split(head);
            return merge(sortList(head), sortList(newHead));
            
        }
    };
    

    Then to achieve O(1) space, we can implement the above recursive version in a bottom-up iterative way.
    We divide the list into sub-lists with the length of len (len starting with 1) and then we merge-sort two consecutive sub-lists. Then we double len and merge-sort two consecutive sub-lists, which are the resulting sublists from the previous merge-sort Then we continue...

    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if(!head || !head->next) return head;
            ListNode dummy(0),*newHead, *tail1, *tail2, *temp;
            dummy.next = head;
            
            int len=1, merge, i;
            
            do{
                merge =0; // number of mergesort it does in the current iteration
                head = &dummy;
                do
                {
                    ++merge;
                    tail1 = head;
                    for(i=0;i<len && tail1->next;++i) tail1 = tail1->next; // get the first half sub-list to be merged
                    if(i<len || !tail1->next) break; // if it reaches the end, jump out the inner loop
                    newHead = tail1->next;  
                    tail2 = newHead;  // find the second half sub-list
                    for(i=0;i<len && tail2;++i) tail2 = tail2->next;
                    tail1->next = tail2;  // note set tail1s next to tail2 to ensure the last node of the resulting list will still link to the rest of the list.
                    while(newHead!=tail2) //merge two sorted sublists
                    {
                        if(head->next!=tail2 && head->next->val<=newHead->val) head =head->next;
                        else swap(newHead, head->next);
                    }
                    while(head->next!=tail2) head = head->next; // move to the rest of the list
                }while(tail2);    
                len =2*len;
            }while(merge>1); // if there are at least two sublists to be merged.
            return dummy.next;
         }
    };

Log in to reply
 

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