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

class Solution {
public:
    ListNode* mergeTwoList(ListNode* head1,ListNode* head2){
        //合并二个链表,返回合并后链表的头指针
        if(head1 == nullptr  || head2 == nullptr){
            //head1为空返回head2，head2为空返回head1
            //head1和head2都为空返回nullptr
            return head1 == nullptr ? head2 : head1; 
        }
        //head1和head2都不为空，开始合并这两个链表
        ListNode* newHead = new ListNode(0);
        ListNode* ptr = newHead;
        while(head1 && head2){
            if(head1->val < head2->val){
                ptr->next = head1;
                head1=head1->next;
            }else {
                ptr->next = head2;
                head2 = head2->next;
            }
            ptr = ptr->next;
        }
        if(head1){
            ptr->next = head1;
        }
        if(head2){
            ptr->next = head2;
        }
        return newHead->next;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.size() == 0){
            return  nullptr;
        }
        if(lists.size() == 1){//只有一条链表直接返回
            return lists[0];
        }
        if(lists.size() == 2){//两条链表调用mergeTwoLists函数即可
            return mergeTwoList(lists[0], lists[1]);
        }
        //3条链表及以上
        int n = lists.size() /2;
        //分治法：将一个vector划分为两个vector
        vector<ListNode*> list1;
        vector<ListNode*> list2;
        for(int i = 0;i<n;++i){
            list1.push_back(lists[i]);
        }
        for(int i = n;i<lists.size();++i){
            list2.push_back(lists[i]);
        }
        //分别对两个vector调用mergeKlists函数，最后返回链表头
        ListNode* head1 = mergeKLists(list1);
        ListNode* head2 = mergeKLists(list2);
        //对两个链表使用mergeTwoLists函数合并即可
        return mergeTwoList(head1, head2);
    }
};