LeetCode 23. Merge k Sorted Lists | LeetCode 努力解題中

題目在這兒~

以下為個人解題思路，不一定是最好的解法，但應該還是有用~

兩數列合併

如果是兩個已排序數列，可以用以下方法合併。
每次比較兩數列的開頭，將數字較小的放入已排序數列並從原本的數列刪除，一直重複到有一數列空了，再把剩餘的數字補到最後。

step 1 step 2 step 3 step 4 step 5 動畫版本

可以先到 這題 練習個~

數列兩兩合併

有多個數列時，只要一直兩兩合併，最後就會得到一個已排序的數列。方法有蠻多種的，可以向 merge sort 一樣每次分一半再合併，這裡用比較簡單的方法，vector 的前兩個先合併，然後塞到 vector 的最後，直到剩一個數列。

程式碼

// use c++
class Solution {
public:
    ListNode* merge(ListNode* list1, ListNode* list2){
        // 如果有一數列空了，不用排序
        if(list1 == NULL){
            return list2;
        }
        if(list2 == NULL){
            return list1;
        }

        // 設定新數列的起始節點(head)
        ListNode* head, *now;
        if(list1->val < list2->val){
            head=now=list1;
            list1=list1->next;
        }
        else{
            head=now=list2;
            list2=list2->next;
        }

        // 重複將 val 小的接到新的數列
        while(list1 != NULL && list2 != NULL){
            if(list1->val < list2->val){
                now->next=list1;
                now=list1;
                list1=list1->next;
            }
            else{
                now->next=list2;
                now=list2;
                list2=list2->next;
            }
        }

        // 如果數列有剩，也接到最後
        if(list1 != NULL){
            now->next=list1;
        }
        if(list2 != NULL){
            now->next=list2;
        }
        return head;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 沒有數列，回傳 NULL
        if(lists.size() == 0){
            return NULL;
        }

        // 重複兩兩合併，vector 的前兩個合併，合併後塞到最後
        while(lists.size()>= 2){
            lists.push_back(merge(lists[0], lists[1]));
            lists.erase(lists.begin(), lists.begin()+2);
        }
        return lists[0];
    }
};