题解 | #合并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* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        if(lists.empty()) return nullptr;

        auto it=lists.begin();
        ListNode* LL=*it;
        while (it!=lists.end()-1) 
        {
            it++;
            LL=Merge(LL, *it);  
          
        }
        return LL;
    }
    ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
    {
        if(pHead1==nullptr&&pHead2==nullptr) return nullptr;
        if(pHead1==nullptr) return pHead2;
        if(pHead2==nullptr) return pHead1;

        ListNode* LL=new ListNode(pHead1->val);
        ListNode* R=LL;
        while (pHead1!=nullptr&&pHead2!=nullptr) 
        {
            if(pHead1->val<pHead2->val)
            {
                ListNode* n=new ListNode(pHead1->val);
                LL->next=n;
                LL=LL->next;
                pHead1=pHead1->next;
           
            }
            else {
                ListNode* n=new ListNode(pHead2->val);
                LL->next=n;
                LL=LL->next;

                pHead2=pHead2->next;
            }
        }
        if(pHead1)
            LL->next=pHead1;
        else
            LL->next=pHead2;

         return R->next;
    }

    
};