It seems that sortList.cpp does not meet the requirement of constant space complexity. about leetcode HOT 5 OPEN

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;
    }
};