My recursive Merge sort solution


  • 1
    Y

    BreakList use a "fast slow pointer to find the middle of a single list. The idea is pretty simple, every time, fast pointer advance twice, slow pointer advance only 1. ratio is 1/2.
    Once the list was split at the middle, then just recursively call mergeSort.
    once it get sorted. then just recursively merge two sorted list. I suggest do this one first(merge two sorted lists) https://oj.leetcode.com/problems/merge-two-sorted-lists, if you don't understand this solution.

       class Solution {
            void breakList(ListNode *head, ListNode **a, ListNode **b) {
                *a = *b = NULL;
                ListNode *fast, *slow;
        
                if (!head)
                    return;
                if (!head->next) {
                    *a = head;
                    return;
                }
                slow = head;
                fast = head->next;
                while (fast) {
                    fast = fast->next;
                    if (fast) {
                        slow = slow->next;
                        fast = fast->next;
                    }
                }
                *a = head;
                *b = slow->next;
                slow->next = NULL;
            }
        
            ListNode *doMerge(ListNode *a, ListNode *b) {
                if (!a)
                    return b;
                if (!b)
                    return a;
        
                if (a->val < b->val) {
                    a->next = doMerge(a->next, b);
                    return a;
                } else {
                    b->next = doMerge(b->next, a);
                    return b;
                }
            }
            void mergeSort(ListNode **phead) {
                ListNode *a, *b;
                ListNode *head = *phead;
        
                // 0 or 1 element
                if (!head || !head->next)
                    return;
                breakList(head, &a, &b);
                mergeSort(&a);
                mergeSort(&b);
        
                *phead = doMerge(a, b);
            }
        public:
            ListNode *sortList(ListNode *head) {
                mergeSort(&head);
                return head;
            }
        };

  • 0
    K

    Unfortunately the space complexity is O(log n) not O(n)... Think it as stack. I am not sure if there's a way to really use constant space.


Log in to reply
 

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