My recursive Merge sort solution

  • 1

    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), 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)
                if (!head->next) {
                    *a = head;
                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)
                breakList(head, &a, &b);
                *phead = doMerge(a, b);
            ListNode *sortList(ListNode *head) {
                return head;

  • 0

    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.