合并2个有序链表=> 进阶 合并k个有序链表---C++实现

合并2个有序链表三种方法
LeetCode OJ链接(戳我)
一般方法

有合并2个链表作为前提，再来看这题简直是简单，最简单容易想到该方法。
该方法固然可行，但是是两两合并链表，时间复杂度O(nk)(n是链表个数，k是链表长度)空间复杂度O(1)。显然，时间复杂度还不够低，应该优化。

node* mergeKLists(vector<node*>& lists) {
	if (lists.empty())
		return nullptr;
	node *ans = nullptr;
	for (node* p : lists)
		ans = mergeTwoLists(ans, p);
	return ans;
}

改进

利用归并排序的思路，每次将k个链表分成两部分，对这2个部分的返回值再调用mergeTwoList方法，也就是分而治之的思想(DIvide
And Conquer)

ListNode* mergeKLists(vector<ListNode*>& lists) {
	if (lists.empty())
		return nullptr;
	if (lists.size() == 1)
		return lists[0];
	if (lists.size() == 2)
		return mergeTwoLists(lists[0], lists[1]);
	int mid = lists.size() >> 1;
	//这里初始化vector的时候设置好size，防止扩容发生拷贝构造和析构，
	//我在leetcode上尝试了一下，提前设置好size比vector<int> v1,v2这种声明要快20ms
	vector<node*> v1(mid, nullptr), v2(lists.size() - mid, nullptr);
	int i, j, k;
	i = j = k = 0;
	for (; i < mid; ++i)
		v1[j++] = lists[i];
	for (; i < lists.size(); ++i)
		v2[k++] = lists[i];
	node *p1 = mergeKLists(v1);
	node *p2 = mergeKLists(v2);
	return mergeTwoLists(p1, p2);
}

最后

以上就是现代美女为你收集整理的合并2个有序链表=> 进阶 合并k个有序链表---C++实现的全部内容，希望文章能够帮你解决合并2个有序链表=> 进阶 合并k个有序链表---C++实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。