题解 | #合并k个已排序的链表#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
    ListNode *merge(ListNode *pHead, ListNode *qHead)
    {
        ListNode *res = new ListNode(0);
        ListNode *tail = res;
        ListNode *p=pHead, *q=qHead;
        while(p || q)
        {
            if(p && q)
            {
                if(p->val < q->val){auto tmp = p; p = p->next; tail->next = tmp;}
                else {auto tmp = q; q = q->next; tail->next = tmp;}
                tail = tail->next;
            }
            else if(p)
            {auto tmp = p; p = p->next; tail->next = tmp; tail = tail->next;}
            else if(q)
            {auto tmp = q; q = q->next; tail->next = tmp; tail = tail->next;}
        }
        auto ret = res->next;
        delete res;
        return ret;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return nullptr;
        if(lists.size() == 1) return lists[0];
        auto leftlists = 
        vector<ListNode*>(lists.begin(), lists.begin() + lists.size() / 2);
        auto left = mergeKLists(leftlists);
        auto rightlists = 
        vector<ListNode*>(lists.begin() + lists.size() / 2, lists.end());
        auto right = mergeKLists(rightlists);
        return merge(left, right);
    }
};