I believe this is a pretty hard one.

The idea is to use merge sort (toke me a bit of time to prove it’s O(n log n) and quite some time to debug…). Since recursion is also space-expensive, we use while loop to replace recursion.

Here’s the code… pretty long this time. And I think this code is a bit ugly. Don’t know how to beautify it yet.

class Solution {
public:
    ListNode *sortList(ListNode *head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int cnt = 0;
        ListNode *node = head;
        while(node != NULL){ cnt++; node = node->next; }
        
        int lvl = 1;
        while(lvl < cnt){
            node = head; ListNode *prev = NULL;

            while(node != NULL){
                ListNode *start = node;

                for(int i = 0 ; i < lvl && node != NULL; i++)
                    node = node->next;

                ListNode *middle = node, *tail = NULL;

                for(int i = 0 ; i < lvl && node != NULL; i++)
                    node = node->next;

                ListNode *nhead = merge(start, middle, lvl, &tail);
                
                if(prev == NULL) head = nhead;
                else prev->next = nhead;

                prev = tail;
            }

            if(prev != NULL) prev->next = NULL;

            lvl <<= 1;

        }
        return head;
    }
    
    ListNode *merge(ListNode *l1, ListNode *l2, int lvl, ListNode **tail){
        int c1 = 0, c2 = 0;
        if(l1 == NULL || l2 == NULL){return l1; *tail = NULL;}

        ListNode *node = NULL,*head = NULL;

        while((c1 < lvl)  && (l2 != NULL) && (c2 < lvl)){
            ListNode *result;
            if(l1->val < l2->val){
                result = l1; c1++; l1 = l1->next;
            } else{
                result = l2; c2++; l2 = l2->next;
            }
            
            if(node != NULL){
                node->next = result; 
            } else{
                head = result;
            }
            
            node = result;
        }
        
        while(c1 < lvl){
            node->next = l1; node = l1;
            c1++; l1 = l1->next;
        }
        while((c2 < lvl) && (l2 != NULL)){
            node->next = l2; node = l2;
            c2++; l2 = l2->next;
        }
        
        *tail = node;
        return head;

    }
};