• Problem Link: [↗]
• Difficulty: 🔴 Hard
• Problem description:

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

1. Example 1:

   Input: lists = [[1,4,5],[1,3,4],[2,6]]
   Output: [1,1,2,3,4,4,5,6]

2. Example 2:

   Input: lists = []
   Output: []

3. Example 3:

   Input: lists = [[]]
   Output: []

思路

基本上有兩個重點： 1. Merge sorted lists: 如何用 O(m+n) 的時間將長度為 m 與 n 的 sorted list 合併為一條。 這不難，分別用兩個指標遍歷兩個 Lists ，把數值較小的接到結果後面。 若有一個比較早結束，就直接把另一個剩下的部份接到結果後面。 2. Divide and conquer: 減少每次合併時候處裡的 List 長度。 不依序將 k 個 Lists 接起來，而是先每 2 個接、每 4 個接…。

不明白為什麼是 Hard …

Merge sorted lists

演算法不難，那就來努力寫漂亮的程式碼吧！

static ListNode* merge(ListNode* a, ListNode* b) {
    ListNode *result = nullptr, **link = &result;
    while(a && b){
        auto& p = (a->val < b->val)? a : b;
        *link = p->next;
        link = &((*link)->next);
        p = p->next;
    }
    *link = (a)? a : (b)? b : nullptr;
    return result;
}

1. 如同上次所題，空指標可視為長度零的 link-list，雙重指標可以當作「指向結果的接口的指標」。
2. 利用 reference （第 4 行），來操作要被加進結果的 node，減少更新被拔掉的 List 的指標時的判斷。

Divide and conquer

ListNode* mergeKLists(vector<ListNode*>& lists) {
    int n = lists.size();
    for(int len = 2; len <= 2*n; len *= 2)
        for(int i = 0, j = i + len/2; j < n ; i += len, j += len)
            lists[i] = merge(lists[i], lists[j]);
    return n ? lists[0] : 0;
}

基本上就是把 index 數好就好，不過要注意在輸入為 [] 的時候需要特別判斷。

使用 std::reduce

另外因為上面寫的 merge 同時有交換律與結合律，也就是對所有的 a, b, c $$ merge(a,b) = merge(b,a) \\\\ merge(a,merge(b, c)) = merge(merge(a, b),c) $$ 因此可以使用 STL 的 std::reduce，它是 Cpp17 加入的演算法，並在 Cpp20 成為平行演算法之一。 會要求交換律與結合律是因為 std::reduce 能以任意的順序來結合（？）每個元素（詳情可見 std::accumulate vs. std::reduce）。

ListNode* mergeKLists(vector<ListNode*>& lists) {
    return std::reduce(std::execution::par, std::begin(lists), std::end(lists),
                        static_cast<ListNode*>(nullptr), Solution::merge);
}

另外由於初始值（上面的 nullptr）的型別會直接作為回傳值（與中間值）的型別，所以需要特別轉型成 ListNode*。

其中的 std::execution::par 是 Cpp20 加入的平行化策略（？），另外還有 seq、unseq 以及 par_unseq 幾種策略可以選擇。

使用遞迴

ListNode* mergeKLists(const vector<ListNode*>& lists) {
    if(int n = lists.size(); n == 0)
        return nullptr;
    else if(n == 1)
        return lists.front();
    else{
        auto a = std::begin(lists),
             b = std::end(lists),
             m = std::next(a, std::distance(a, b)/2);
             //= std::midpoint(a, b) // Cpp20
        return merge(Recursive({a, m}), Recursive({m, b}));
    }
}

這個寫法有個問題，因為遞迴的時候會複製新的 std::vector<ListNode*> ，這也表示參數一定要用 const reference ，不能用 reference。不過在 Cpp 20 應該可以用 std::ranges 解決這些問題，（或是要自己定一個類似的 struct 也不難）。

Full Solution