Sort a linked list in O(n log n) time using constant space complexity.

This one is easy. Merge sort can solve this problem.

See the following code for the merge sort from bottom to top

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *loop_list(ListNode *head, int len){
        // There are len nodes from head(inclusive) to ret(exclusive)
        while(head != NULL && len-- > 0) head = head -> next;
        return head;
    }
   
    ListNode *merge(ListNode *head, int len){
        // Merge len nodes beginning from head->next(inclusive), and return the last node.
        if(head == NULL || head -> next == NULL) return NULL;
       
        ListNode *a_beg = head -> next;
        ListNode *a_end = loop_list(a_beg, len/2 - 1);
        if(!a_end) return NULL;
       
        ListNode *b_beg = a_end -> next;
        a_end -> next = NULL;
       
        ListNode *b_end = loop_list(b_beg, len/2 - 1);
        ListNode *new_end = b_end == NULL ? NULL : b_end -> next;
        if(b_end != NULL) b_end -> next = NULL;
       
        ListNode *loop = head;
        ListNode *a_loop = a_beg;
        ListNode *b_loop = b_beg;
        while(a_loop || b_loop){
            ListNode *next;
            if(!a_loop) {
                next = b_loop;
            }
            else if(!b_loop){
                next = a_loop;
            }
            else next = (a_loop -> val < b_loop -> val) ? a_loop : b_loop;
            loop -> next = next;
            loop = loop -> next;
           
            if(next == a_loop){
                a_loop = a_loop -> next;
            }
            else if(next == b_loop){
                b_loop = b_loop -> next;
            }
        }
        loop -> next = new_end;
        return loop;
    }
   
    ListNode *sortList(ListNode *head) {
        ListNode *fake_head = new ListNode(0);
        fake_head -> next = head;
        int num_merge = 0;
        for(int len = 2; true; len *= 2){
            num_merge = 0;
            ListNode *loop = fake_head;
            while(loop && loop->next){
                loop = merge(loop, len);
                num_merge ++;
            }
            if(num_merge <= 1) break;
        }
        head = fake_head -> next;
        delete fake_head;
        return head;
    }
};