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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    //合并两个链表
    ListNode* merge(ListNode* p1,ListNode* p2)
    {
        if(!p1 || !p2)  return p1==nullptr ? p2 : p1;
        auto head = new ListNode(0);
        ListNode* cur = head;
        while(p1 && p2)
        {
            if(p1->val <= p2->val){
                cur->next = p1;
                p1 = p1->next;
            }
            else{
                cur->next = p2;
                p2=p2->next;
            }
            cur = cur->next;
        }
        if(p1) cur->next = p1;
        else cur->next = p2;
        return head->next;
    }
  
    //合并left 到 right 范围内的链表
    ListNode*  dividemerge(vector<ListNode*>& lists,int left,int right)
    {
        if(left > right) return nullptr;
	   //left == right 说明只有一个链表,返回即可
        else if(left == right) return lists[left];
	  //大于一个链表
        else{
            int mid = left + ((right-left)>>1);
		   //我让他左边去合并,合并好后返回头节点
            ListNode* left_ok = dividemerge(lists,left,mid);
		  //我让他右边去合并,合并好后返回头节点
            ListNode* right_ok = dividemerge(lists,mid+1,right);
		   //我再让 左边合并好的 和 右边合并好 合并一起,返回头节点
            return merge(left_ok,right_ok);
        }
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
       return dividemerge(lists,0,lists.size()-1); 
    }
};