leetcode 23: Merge k Sorted Lists

這次的題目是合併 K 個已排序的串列，一開始先試著直接把所有元素串在一起，放進一個陣列後排序完再填進串列 結果長得像這樣：

#include <stdlib.h>

int cmp(const void* a, const void* b)
{
    return *(int*)a - *(int*)b;
}

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
    struct ListNode *ret = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *tail = ret;
    int sz = 0;

    for(int i=0 ; i<listsSize ; i++)
    {
        struct ListNode *idx = lists[i];
        while(idx)
        {
            // update
            tail->next = idx;
            tail = tail->next;
            idx = idx->next;
            sz++;
        }
    }

    // special case
    if(sz == 0) return NULL;

    // remove first node cuz it is empty
    tail = ret;
    ret = ret->next;
    free(tail);

    int* arr = (int*)malloc(sizeof(int)*sz);
    tail = ret;
    sz = 0;

    // copy and sort
    while(tail)
    {
        arr[sz++] = tail->val;
        tail = tail->next;
    }
    qsort(arr, sz, sizeof(int), cmp);

    tail = ret;
    sz = 0;

    // copy and free
    while(tail)
    {
        tail->val = arr[sz++];
        tail = tail->next;
    }
    free(arr);

    return ret;
}

結果 $16ms/8MB$ ，其實還算不錯，只是 code 略長，另外也沒有用到所有串列皆已排序的性質 在這裡改用依序合併兩個串列的方式，因為皆已排序，所以只要比較首元素，將較小的接在前面，之後再遞迴得合併其餘元素就好，code 如下：

struct ListNode* mergeTwoLists(struct ListNode* a, struct ListNode* b)
{
    if(!a && !b) return NULL;
    if(a && !b) return a;
    if(b && !a) return b;

    if(a->val < b->val)
    {
        a->next = mergeTwoLists(a->next, b);
        return a;
    }
    else
    {
        b->next = mergeTwoLists(a, b->next);
        return b;
    }
}

每個元素都會掃過一遍，所以合併的複雜度是 $O(|a|+|b|)$ 接下來是要合倂所有串列的部分，依序兩兩合併的 code 非常短，長這樣：

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
    if(listsSize == 0) return NULL;

    for(int i=1 ; i<listsSize ; i++)
    {
        lists[i] = mergeTwoLists(lists[i-1], lists[i]);
    }
    return lists[listsSize-1];
}

但這樣的總複雜度是 $O(Nk)$ ， $N$ 是最後的串列總長， $k$ 是串列數量，因為串列越來越長，在合併時會拖慢速度 這樣子 submit 的結果是 $204ms/8.1MB$ 加速的方法是在合併時先從比較短的串列開始合併，所以將修改 code 如下：

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize)
{
    if(listsSize == 0) return NULL;

    int mergedSize;
    while(listsSize != 1)
    {
        mergedSize = (listsSize + 1) / 2;
        for(int i=0 ; i<mergedSize ; i++)
        {
            if(2*i+1 >= listsSize)
                lists[i] = lists[2*i];
            else
                lists[i] = mergeTwoLists(lists[2*i], lists[2*i+1]);
        }
        listsSize = mergedSize;
    }

    return lists[0];
}

這裡的 code 更改了合併的順序，是讓相鄰兩串列兩兩合併，示意圖如下

這樣的順序，讓串列的長度比較不會那麼極端，結果確實快了不少 $(16ms/8.1MB)$ 雖然說建個 heap 保證每次都合併最短的兩個串列就能保證比較次數最少，但是會讓空間複雜度上升到 $O(k)$ ，也會產生額外的時間開銷，我想在通常情況下，上述方法應該是足夠快速了

題外話，這題用 python 也可以寫的很短：

class Solution:
    def mergeKLists(self, lists: 'List[ListNode]') -> 'ListNode':
        r = []
        for l in lists:
            while l:
                r.append(l.val)
                l = l.next
        return sorted(r)

結果 98.14%，感覺上面的時間都白費了