23. Merge k Sorted Lists

解題思路

如果考慮一次 merge k 的太麻煩，就兩兩 merge 來簡化問題。

merge 的部分偷懶用遞迴，有機會的話改成非遞迴的版本。

程式碼

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return nullptr;
        while(lists.size() > 1)
        {
            lists.push_back(merge2Lists(lists[0], lists[1]));
            lists.erase(lists.begin());
            lists.erase(lists.begin());
        }
        return lists[0];
    }
    ListNode* merge2Lists(ListNode* l1, ListNode* l2)
    {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val <= l2->val)
        {
            l1->next = merge2Lists(l1->next, l2);
            return l1;
        }
        else
        {
            l2->next = merge2Lists(l1, l2->next);
            return l2;
        }
    }
};