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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cstddef>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
     ListNode* Merge2(ListNode* phead1,ListNode* phead2){
        if(!phead1) return phead2;
        if(!phead2) return phead1;
        ListNode *newhead = new ListNode(0);
        ListNode *begin = newhead;
        ListNode *tmp = NULL;
        while (phead1&&phead2) {
            if(phead1->val<=phead2->val){
                tmp = phead1->next;
                begin->next = phead1;
                phead1 = tmp;
            }
            else{
                tmp = phead2->next;
                begin->next = phead2;
                phead2 = tmp;
            }
            begin = begin->next;
            if(!phead2) begin->next = phead1;
            if(!phead1) begin->next = phead2;
        }
        newhead = newhead->next;
        return newhead;
     }
     ListNode* divideMerge(vector<ListNode*> &lists,int left,int right){
        if(left > right){
            return NULL;
        }
        if(left==right){
            return lists[right];
        }
        int mid = (left + right) / 2;
        return Merge2(divideMerge(lists,left,mid), divideMerge(lists,mid+1,right));
     }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return divideMerge(lists,0,lists.size()-1);
        // write code here
    }
};