0148. Sort List.md

0148. Sort List, medium, , freq: 42%, acceptance: 36.4%

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

Example 1:

Input: 4->2->1->3 Output: 1->2->3->4 Example 2:

Input: -1->5->3->4->0 Output: -1->0->3->4->5

[-84,142,41,-17,-71,170,186,183,-21,-76,76,10,29,81,112,-39,-6,-43,58,41,111,33,69,97,-38,82,-44,-7,99,135,42,150,149,-21,-30,164,153,92,180,-61,99,-81,147,109,34,98,14,178,105,5,43,46,40,-37,23,16,123,-53,34,192,-73,94,39,96,115,88,-31,-96,106,131,64,189,-91,-34,-56,-22,105,104,22,-31,-43,90,96,65,-85,184,85,90,118,152,-31,161,22,104,-85,160,120,-31,144,115] [4,2,1,3] [4,2,5,3,1] [4] []

// 48ms, 56% 
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    ListNode* advance(ListNode* head, int step) {
        for (int i = 1; i < step && head; i++) {
            head = head->next;
        }
        if (!head) return head;
        auto* res = head->next;
        head->next = nullptr;
        return res;
    }
    ListNode* merge(ListNode* l, ListNode* r, ListNode* head) {
        while (l && r) {
            if (l->val < r->val) {
                head = head->next = l;
                l = l->next;
            } else {
                head = head->next = r;
                r = r->next;
            }
        }
        while (l) { head = head->next = l; l = l->next; }
        while (r) { head = head->next = r; r = r->next; }
        return head;
    }
    
public:
    ListNode* sortList(ListNode* head) {
        if (!head) return head;
        
        int len = 0;
        auto p = head;
        while (p) {
            len++;
            p = p->next;
        }
        ListNode dummyHead(0);
        for (int step = 1; step < len; step *= 2) {
            auto tail = head;
            auto newHead = &dummyHead;
            while (tail) {
                auto left = tail;
                auto right = advance(left, step);
                tail = advance(right, step);
                newHead = merge(left, right, newHead);
            }
            head = dummyHead.next;
        }
        return head;
    }
};