C++ Non-recursive merge sort, O(nlogn) time, O(1) space


  • 1
    A

    All recursive solutions do not satisfy the "constant space complexity" requirement.

    15 / 15 test cases passed
    Status: Accepted
    Runtime: 49 ms

    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            if (!head || !head->next) return head;
            ListNode *l1, *l2, *n, **t, **m, **h = &head;
            uint i, c = 1;
            while (1) {
                for (i = 0, m = h; i < c && *m; i++, m = &(*m)->next);
                if (i < c || !*m) {
                    if (*h == head) return head;
                    else { c *= 2; h = &head; continue; }
                }
                for (i = 0, t = m; i < c && *t; i++, t = &(*t)->next); 
                n = *t, l1 = *h, l2 = *m;
                *m = *t = NULL;
                while (l1 && l2) {
                    if (l1->val < l2->val) { *h = l1; l1 = l1->next; }
                    else { *h = l2; l2 = l2->next; }
                    h = &(*h)->next;
                }
                *h = l1 ? l1 : l2;
                while (*h) h = &(*h)->next;
                *h = n;
            }
        }
    };
    

Log in to reply
 

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