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

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

Merge k sorted 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)
		{
			//nextNode = small->next;
			cura->next = small;
			cura=cura->next;
			//small->next = NULL;
			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);/*
					    pn = &head;
					    for(; pn!=NULL; )
					    {
					    cout<<pn->val<<" ";
					    pn=pn->next;
					    }
					    cout<<endl;
					    */

		Solution solu;
		pn = solu.mergeKLists(lists);

		//pn = &head;
		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";
}

总结：

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