148. Sort List

題目網址：https://leetcode.cn/problems/sort-list/

題意：給一 linked list 的起始節點 head, 返回以升序排列過的 linked list。

進階：設計 $O(n \cdot log(n))$ time 且 $O(1)$ space 的演算法

Solution 1：

想法：利用 Merge Sort (top-down)

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 0 或 1 個 node
        if (!head || !head->next) {
            return head;
        }

        // 讓 slow 指向中點; 若 n 為偶數, 則指向第一個中點
        ListNode *slow = head;
        ListNode *fast = head->next;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        ListNode *mid = slow->next; // 右半部分
        slow->next = nullptr; // 左半部分的結尾設為 NULL

        return merge(sortList(head), sortList(mid));
    }

private:
    ListNode* merge(ListNode* l1, ListNode* l2){
        ListNode *dummy = new ListNode(), *tail = dummy;

        while (l1 && l2) {
            // 讓 l1 始終指向較小的 node
            if (l1->val > l2->val) {
                swap(l1, l2);
            }

            tail->next = l1;
            l1 = l1->next;
            tail = tail->next;
        }

        // 這邊可寫成 tail->next = l2; 因為 l1, l2 一開始一定皆不為 NULL
        tail->next = l1 ? l1 : l2;

        return dummy->next;
    }
};

• time：$O(n \cdot log(n))$ ➔ Merge Sort 的時間複雜度, $T(n) = 2 \cdot T(\dfrac{n}{2}) + O(n)$
  • 每回合的合併需要花：$O(n)$
  • 回合數：$O(log(n))$
• space：$O(n)$ ➔ $O(n + log(n))$
  • $O(n)$：merge 後的 linked list 長度最多為 n
  • $O(log(n))$：取決於遞迴深度, 最大遞迴深度為 log(n)

Solution 2：

想法：利用 Merge Sort (bottom-up)

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 0 或 1 個 node
        if (!head || !head->next) {
            return head;
        }

        const int len = getLen(head);
        ListNode *dummy = new ListNode(0, head);

        // log(n) 回合 : 2^0 ~ 2^(log(n)-1) => (log(n) - 1) - 0 + 1 = log(n)
        for (int n = 1; n < len; n <<= 1) {
            // 不能寫 cur = head, 因為 dummy->next 會因 tail 而改變
            ListNode *cur = dummy->next;
            ListNode *tail = dummy;

            while (cur) {
                ListNode *left = cur;
                ListNode *right = split(left, n);
                cur = split(right, n);
                const auto merged = merge(left, right);
                tail->next = merged.first;
                tail = merged.second;
            }
        }
        return dummy->next;
    }

private:
    int getLen(ListNode* head){
        int len = 0;
        while (head) {
            ++len;
            head = head->next;
        }
        return len;
    }

    ListNode* split(ListNode* head, int n){
        while (--n && head) {
            head = head->next;
        }

        ListNode *rest = head ? head->next : nullptr;

        if (head) { // 將左半部分的結尾設為 NULL
            head->next = nullptr;
        }

        return rest;
    }

    pair<ListNode*, ListNode*> merge(ListNode* l1, ListNode* l2){
        ListNode *dummy = new ListNode(), *tail = dummy;
        while (l1 && l2) {
            // 讓 l1 始終指向較小的 node
            if (l1->val > l2->val) {
                swap(l1, l2);
            }

            tail->next = l1;
            l1 = l1->next;
            tail = tail->next;
        }

        /*
         * 當 list 只有一個元素時, l1 不為 NULL, 但 l2 為 NULL, 並不會進入 while loop
         * e.g. [1, 2, 3] => left = [1, 2], right = [3] = cur
         * cur 不為 null, 進入第二個 while loop
         * 此時 left = [3], right = null, 並不會進入 merge 的 while loop
         * 這邊不可寫成 tail->next = l2; 因為不保證一定進 while loop
         */
        tail->next = l1 ? l1 : l2;

        // tail 到達 merged list 的最後一個非 null 的元素
        while (tail->next) {
            tail = tail->next;
        }

        return {dummy->next, tail};
    }
};

• time：$O(n \cdot log(n))$ ➔ Merge Sort 的時間複雜度
• space：$O(1)$ ➔ 用 loop 模擬 recursive, 因此只需常數空間