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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

// 想起了归并排序 
class Solution {
public:
    // BM4 合并两个有序链表
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
		
		ListNode *ans = new ListNode(-1);
		ListNode* curr = ans;
		

		while(pHead1!=nullptr && pHead2!=nullptr)
		{
			if(pHead1->val<=pHead2->val)
			{
				curr->next = pHead1;
				pHead1 = pHead1->next;
			}
			else
			{
				curr->next = pHead2;
				pHead2 = pHead2->next;
			}
			curr = curr->next;
		}

		//当至少有一个链表到头后

		curr->next = pHead1?pHead1:pHead2;

		return ans->next;
        
    }

	ListNode* fenzhi(vector<ListNode *> &lists, int l, int r)
	{
		if(l>=r) //注意这里 比如合并的就是 l[0] l[0] 那返回的还是此链表！
			return lists[l];
		
		int mid = (r+l)/2;

		// 二分
		ListNode* h1 = fenzhi(lists, l, mid);
		ListNode* h2 = fenzhi(lists, mid+1, r);
		// 再两个新链表的合并
		ListNode* mh = Merge(h1, h2);

		return mh;

	}
    ListNode *mergeKLists(vector<ListNode *> &lists) {

        int k = lists.size();
        if(k==0)
        {
            return nullptr;
        }
        if(k==1)
        {
            return lists[0];
        }

		ListNode* ans =  fenzhi(lists, 0, k-1);

		return ans;

        
    }
};

利用BM20中归并排序的模板 并使用合并两个链表的子函数 就通过了 注意改动过的地方