148. Sort List

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

// Top-Down Mergesort
ListNode* merge(ListNode *l1, ListNode *l2) {
    ListNode *dummy = new ListNode(-1e7), *pre = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            pre->next = l1;
            l1 = l1->next;
        } else {
            pre->next = l2;
            l2 = l2->next;
        }
        pre = pre->next;
    }
    if (l1) pre->next = l1;
    else if (l2) pre->next = l2;
    ListNode *res = dummy->next;
    delete dummy;
    return res;
}
ListNode* sortList(ListNode* head) { // time: O(nlogn); space: O(logn)
    if (!head || !head->next) return head;
    // Use slow and fast pointers to find the middle point and separate into two halves
    ListNode *slow = head, *fast = head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = nullptr;
    ListNode *l1 = sortList(head), *l2 = sortList(fast);
    return merge(l1, l2);
}

// Divide the list into two parts
// where the first part includes n nodes
// and return the second part's head
ListNode* split(ListNode* head, int n) {
    for (int i = 1; head && i < n; ++i) head = head->next;
    if (!head) return nullptr;
    ListNode* second_head = head->next;
    head->next = nullptr;
    return second_head;
}

// Merge two lists and append the merged sorted list to the head node
// Finally return the tail of the merged list
ListNode* merge(ListNode* l1, ListNode* l2, ListNode* head) {
    ListNode *cur = head;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    if (l1) cur->next = l1;
    else if (l2) cur->next = l2;
    while (cur->next) cur = cur->next;
    return cur;
}

// Bottom-Up Mergesort
ListNode* sortList(ListNode* head) { // time: O(nlogn); space: O(1)
    if (!head || !head->next) return head;
    
    // Calculate length
    ListNode* cur = head;
    int len = 0;
    while (cur) {
        ++len;
        cur = cur->next;
    }
    ListNode* dummy = new ListNode(-1e7), *left = nullptr, *right = nullptr, *tail = nullptr;
    dummy->next = head;
    for (int step = 1; step < len; step <<= 1) {
        cur = dummy->next;
        tail = dummy;
        while (cur) {
            left = cur;
            right = split(left, step);
            cur = split(right, step);
            tail = merge(left, right, tail);
        }
    }
    ListNode *res = dummy->next;
    delete dummy;
    return res;
}