前置知识：合并两个有序链表：

ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
    if ((!a) || (!b)) return a ? a : b;
    ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
    while (aPtr && bPtr) {
        if (aPtr->val < bPtr->val) {
            tail->next = aPtr; aPtr = aPtr->next;
        } else {
            tail->next = bPtr; bPtr = bPtr->next;
        }
        tail = tail->next;
    }
    tail->next = (aPtr ? aPtr : bPtr);
    return head.next;
}

方法一：顺序合并：

我们可以想到一种最朴素的方法：用一个变量 ans 来维护以及合并的链表，第 i 次循环把第 i 个链表和 ans 合并，答案保存到 ans 中。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b;
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                tail->next = bPtr; bPtr = bPtr->next;
            }
            tail = tail->next;
        }
        tail->next = (aPtr ? aPtr : bPtr);
        return head.next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i) {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }
};

时间复杂度：假设每个链表的最长长度是$n$。在第一次合并后，ans 的长度为$n$；第二次合并后，ans 的长度为$2*n$，第 i 次合并后，ans 的长度为$i*n$。第 i 次合并的时间代价是$O(n+(i−1)×n)=O(i×n)$，那么总的时间代价为$O(\sum_{i=1}^k(i*n))$，故渐进时间复杂度为$O(k^2n)$
空间复杂度：没有用到与 k 和 n 规模相关的辅助空间，故渐进空间复杂度为$O(1)$。

方法二：分治合并

class Solution {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b){
        if((!a)||(!b))return a?a:b;
        ListNode head, *tail = &head, *aptr = a, *bptr = b;
        while(aptr && bptr){
            if(aptr->val>bptr->val){
                tail->next = bptr, bptr = bptr->next;
            } else {
                tail->next = aptr, aptr = aptr->next;
            }
            tail = tail->next;
        }
        if(aptr || bptr){
            tail->next = aptr?aptr:bptr; 
        }
        return head.next;
    }
    ListNode* merge(int l, int r, vector<ListNode*>& lists){
        if(l > r)return nullptr;
        if(l == r)return lists[l];
        int mid = l + r >> 1;
        return mergeTwoLists(merge(l, mid, lists), merge(mid + 1, r, lists));
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int l = 0, r = lists.size() - 1;
        return merge(l, r, lists);
    }
};

时间复杂度：考虑递归「向上回升」的过程——第一轮合并$k/2$组链表，每一组的时间代价是$O(2n)$；第二轮合并$k/4$组链表，每一组的时间代价$O(4n)$……所以总的时间代价是$O(kn×logk)$，故渐进时间复杂度为$O(kn×logk)$。
空间复杂度：递归会使用到$O(logk)$ 空间代价的栈空间。