It seems that sortList.cpp does not meet the requirement of constant space complexity.

[RocFang]

https://github.com/haoel/leetcode/blob/master/src/sortList/sortList.cpp

return mergeTwoLists(sortList(head), sortList(p2));

[haoel]

Yes, the recursive Merge Sort requires O(N) auxiliary space.

If we use non-recursive way, the code might be hard to read.

Anyway, do you have any good solution we can have readable code and good performance both?

[ghost]

:smile: It's simple. Here is my code:

class Solution {
public:
    // The bottom-up merge-sort. (non-recursive)
    ListNode* sortList(ListNode* head) {
        ListNode fakeHead(0);
        fakeHead.next = head;
        int length = 1;
        ListNode* subLeft = fakeHead.next;
        ListNode* subRight = cut(subLeft, length);
        while (subRight != NULL) {
            ListNode* tail = &fakeHead;
            do {  // merge every two adjacent lists
                ListNode* nextSubLeft = cut(subRight, length);
                tail = merge(subLeft, subRight, tail);
                subLeft = nextSubLeft;
                subRight = cut(subLeft, length);
            } while (subLeft != NULL);
            length *= 2;
            subLeft = fakeHead.next;
            subRight = cut(subLeft, length);
        }
        return fakeHead.next;
    }
private:
    ListNode* cut(ListNode* head, int length) {
        while (head != NULL && --length > 0) head = head->next;
        if (head == NULL) return NULL;
        ListNode* next = head->next;
        head->next = NULL;
        return next;
    }
    ListNode* merge(ListNode* l1, ListNode* l2, ListNode* tail) {
        while (l1 != NULL && l2 != NULL) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = (l1 != NULL ? l1 : l2);
        while (tail->next != NULL) tail = tail->next;
        return tail;
    }
};

It can be further optimized if you give it less readability.

[haoel]

@jakwings Wow, you are really good at code, I am too old to read such long code. ;-)

[ghost]

Hey, there are only two new blocks, not that long as it seems. The merge function is trivial, also used in some other problems.

[shreyanshi2228]

@haoel Have a look at this.

class Solution
{
public:
    ListNode *merge(ListNode *l1, ListNode *l2)
    {
        if (!l1)
            return l2;
        if (!l2)
            return l1;

        if (l1->val < l2->val)
        {
            l1->next = merge(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = merge(l1, l2->next);
            return l2;
        }
    }
    ListNode *sortList(ListNode *head)
    {
        if (head == nullptr or head->next == nullptr)
            return head;
        
        //// step 1. cut the list to two halves
        ListNode *slow = head;
        ListNode *fast = head->next;   // yrr isse na second half ka mid consider nhi ho rha jab list even hain uss case meinn 
        while (fast and fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *head2 = slow->next;
        slow->next = nullptr;

        // step 2. divide each parth into further halves          
        ListNode *l1 = sortList(head);
        ListNode *l2 = sortList(head2);

        // step 3. merge l1 and l2
        return merge(l1, l2);
    }
};