`
jgsj
  • 浏览: 951417 次
文章分类
社区版块
存档分类
最新评论

LeetCode Merge K Sorted Lists 问题和解答程序 C++ priority queue实现方法

 
阅读更多

Merge k Sorted Lists

Mergeksorted linked lists and return it as one sorted list. Analyze and describe its complexity.

其实这个问题真没有什么“技巧”;想多了反而不好。不外乎就两种方法吧:

1. 各列数量头一个数组成一个数组,然后取其最大者,插入新的数组。

2. 反复调用两个数组合并的函数k-1次

下面是第一种方法,用了STL容器priority_queue来实现。当然还有很多其他方法实现。要使用这个容器的技巧就是:增加一个adaptNode相当于一个adaptor,使得可以使用priority_queue,否则因为原来的ListNode没有< >的操作而无法使用这个容器的。

#include<iostream>
#include<vector>
#include<functional>
#include<queue>

using namespace std;

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

//For adding operator < and >; So that we can form priority_queue
struct AdaptNode{
	int val;
	ListNode *cur;
	AdaptNode(ListNode *node):cur(node)
	{
		if(node == NULL)
			val = INT_MAX;
		else
		{
			val = node->val;
		}
	}

	bool operator<(const AdaptNode& an)const  
	{  
		return val<an.val;  
	}  
	bool operator>(const AdaptNode& an)const  
	{  
		return val>an.val;  
	}  
};

class Solution {
public:
	ListNode *mergeKLists(vector<ListNode *> &lists) {

		if (lists.empty()) return NULL;

		priority_queue<AdaptNode, vector<AdaptNode>, greater<AdaptNode> > pq(lists.begin(),lists.end());

		ListNode head(0);
		ListNode *cura, *small;
		cura = &head;
		small = pq.top().cur;
		
		while (pq.top().val != INT_MAX)
		{
			cura->next = small;
			cura=cura->next;
			pq.pop();
			pq.push(AdaptNode(small->next));
			small = pq.top().cur;
		}
		return head.next;
	}
};

int main()
	try
{
	{
		ListNode head(0);
		ListNode fir(1);
		ListNode sec(2);
		ListNode thi(3);
		ListNode fou(4);
		ListNode fiv(5);
		ListNode six(6);
		ListNode sev(7);
		ListNode eig(8);
		ListNode nin(9);
		ListNode ten(10);
		ListNode da(6);
		ListNode db(9);
		ListNode dc(10);
		ListNode de(19);
		ListNode df(100);
		ListNode *pHead1;
		ListNode *pHead2;
		ListNode *pHead3;

		pHead1 = &head;
		pHead2 = &six;
		pHead3 = &da;

		da.next = &db;
		db.next = &dc;
		dc.next = &de;
		de.next = &df;

		head.next = &fir;
		fir.next = &sec;
		sec.next = &thi;
		thi.next = &fou;
		fou.next = &fiv;
		fiv.next = NULL;

		six.next = &sev;
		sev.next = &eig;
		eig.next = &nin;
		nin.next = &ten;
		ten.next = NULL;

		vector<ListNode *>lists;
		lists.push_back(pHead1);
		lists.push_back(pHead2);
		lists.push_back(pHead3);

		ListNode *pn(NULL);
		Solution solu;
		pn = solu.mergeKLists(lists);
		for(; pn!=NULL; )
		{
			cout<<pn->val<<" ";
			pn=pn->next;
		}
		cout<<endl;
		return 0;
	}
}
catch(out_of_range)
{
	cerr<<"range error\n";
}
catch(...)
{
	cerr<<"unknow exception thrown\n";
}


总结:

指针操作真是灰常烦。要格外小心!!!

12.13update 更新方法2程序:

注意:ListNode *head;代表没有初始化,而ListNode *head = nullptr;代表已经初始化为nullptr空指针了。

ListNode *mergeKLists2(vector<ListNode *> &lists) {
		if(lists.empty()) return nullptr;
		ListNode *head = lists[0];
		for (int i = 1; i < lists.size(); i++)
		{
			head = mergeTwo(head, lists[i]);
		}
		return head;
	}

	ListNode *mergeTwo(ListNode *n1, ListNode *n2)
	{
		if (!n1) return n2;
		if (!n2) return n1;
		ListNode *t = n1;
		if (n1->val > n2->val)
		{
			t = n2->next;
			n2->next = n1;
			n1 = n2;
			n2 = t;
			t = n1;
		}

		while (t->next && n2)
		{
			if (t->next->val > n2->val)
			{
				ListNode *temp = t->next;
				t->next = n2;
				n2 = n2->next;
				t = t->next;
				t->next = temp;
			}
			else t = t->next;
		}
		if (n2) t->next = n2;

		return n1;
	}

到了现在这种题居然变得这么简单了,实现第二种方法感觉就像势如破竹,一下子通过了。

这种经典的合并程序,基本上可以一口气写出来了,还可以任意变换。以前是不敢想象。

不过这个跟某些网上的所谓达到盲打有点不一样。

我觉得这样的水平不是死背出来的,而是通过做题,然后熟悉基本方法和操作达到的。


2014-1-25

更新个更加简洁点的程序。时间复杂度应该是O(n1+n2+n3...)n1,n2,n3...是lists.size()中各个链表的长度。空间复杂度是O(1)

ListNode *mergeKLists(vector<ListNode *> &lists) 
	{
		if (lists.empty()) return NULL;
		ListNode dummy(0);
		dummy.next = lists[0];

		for (int i = 1; i < lists.size(); i++)
		{
			ListNode *p = &dummy;
			ListNode *t = lists[i];
			while (t && p->next)
			{
				if (t->val < p->next->val)
				{
					ListNode *tmp = t->next;
					t->next = p->next;
					p->next = t;
					p = t;
					t = tmp;
				}
				else p = p->next;
			}
			if (t) p->next = t;
		}
		return dummy.next;
	}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics