148. 鏈表排序

推薦事前閱讀：912. 排序數組

思路

鏈表的排序，可以做到時間複雜度 $O(\log{n})$ ，空間複雜度 $O(1)$ ，使用合併排序，非遞迴版本，以省去堆棧空間。

1. 不論 $\text{step}$ 多少，第一組需要特別找到頭節點（因為數字大小關係會變動）
2. 合併前將指針斷開，方便合併的階段僅移動指針方向，並且紀錄這組排序後的開始與結束節點，以將排好序的組別接回。

程式碼

鏈表

class Solution {
private:
    ListNode* startNode;
    ListNode* endNode;
    // 包括 s 在內，往下數 k 個節點 return
    // 如果不夠，return 最後一個數到的非空節點
    ListNode* findEnd(ListNode* s, int k) {
        while(s->next != nullptr && --k > 0) {
            s = s->next;
        }
        return s;
    }

    // l1...r1 -> null : 有序的左部分
    // l2...r2 -> null : 有序的右部分
    // 整體 merge 在一起，保證有序。
    // 並且把全局變量startNode設置為整體的頭，全局變量endNode設定為整體的尾
    void merge(ListNode* l1, ListNode* r1, ListNode* l2, ListNode* r2) {
        ListNode* pre; // 決定第一個點
        if(l1->val <= l2->val) {
            startNode = l1;
            pre = l1;
            l1 = l1->next;
        }
        else {
            startNode = l2;
            pre = l2;
            l2 = l2->next;
        }
        while(l1 != nullptr && l2 != nullptr) {
            if(l1->val <= l2->val) {
                pre->next = l1;
                pre = l1;
                l1 = l1->next;
            }
            else {
                pre->next = l2;
                pre = l2;
                l2 = l2->next;
            }
        }
        if(l1 != nullptr) {
            pre->next = l1;
            endNode = r1;
        }
        else {
            pre->next = l2;
            endNode = r2;
        }
    }
public:
    ListNode* sortList(ListNode* head) {
        int n = 0;
        ListNode* cur = head;
        while(cur != nullptr) {
            ++n;
            cur = cur->next;
        }

        // l1...r1 每組的左部分
        // l2...r2 每組的又部分
        // next 下一組的開頭
        // lastTeamEnd 上一組的結尾
        ListNode *l1, *l2, *r1, *r2, *next, *lastTeamEnd;
        for(int step = 1; step < n; step <<= 1) {
            // 第一組很特殊，因為要決定整個鏈表的頭，所以單獨處理
            l1 = head;
            r1 = findEnd(l1, step);
            l2 = r1->next;
            // 如果 l2 為空，代表前面已經處理完了
            if(l2 == nullptr) {
                break;
            }
            r2 = findEnd(l2, step);
            next = r2->next; // 下一輪的開始
            
            // 切斷連接，方便 merge
            r1->next = nullptr;
            r2->next = nullptr;

            merge(l1, r1, l2, r2);
            head = startNode;
            lastTeamEnd = endNode; // 此時 endNode -> next = nullptr;
            while(next != nullptr) {
                l1 = next; // 下一組的開始
                r1 = findEnd(l1, step);
                l2 = r1->next;
                if(l2 == nullptr) {
                    lastTeamEnd->next = l1;  // 將上一組的尾端接到現在組別的開頭
                    break;
                }
                r2 = findEnd(l2, step);
                next = r2->next;

                r1->next = nullptr;
                r2->next = nullptr;
                merge(l1, r1, l2, r2);
                lastTeamEnd->next = startNode;
                lastTeamEnd = endNode;
            }
            // 每一輪 step 結束，都要把尾巴封好，避免變成壞或指向舊資料
            lastTeamEnd->next = next;
        }
        return head;
    }
};

2.

複雜度分析

• 時間複雜度：
• 空間複雜度：