Sort List

• Time : $O(nlogn)$
• Space : $O(n)$

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

ListNode* merge(ListNode* A, ListNode* B) {
    ListNode* dummy = new ListNode(-1);
    ListNode* runner = dummy;
    while(A and B) {
        if(A->val < B->val) {
            runner->next = A;
            A = A->next;
        } else {
            runner->next = B;
            B = B->next;
        }
        runner = runner->next;
    }
    if(A) runner->next = A;
    else runner->next = B;

    return dummy->next;
}

ListNode* Solution::sortList(ListNode* A) {
    vector<ListNode*> AA;
    while(A) {
        AA.push_back(A);
        auto nxt = A->next;
        A->next = NULL;
        A = nxt;
    }
    while(AA.size() > 1) {
        vector<ListNode*> AAA;
        for(int i = 0; i < AA.size(); i += 2) {
            if(i + 1 != AA.size()) AAA.push_back(merge(AA[i], AA[i+1]));
            else AAA.push_back(AA[i]);
        }
        swap(AA, AAA);
    }
    return AA[0];
}