LeetCode Merge K Sorted Lists 问题和解答程序 C++ priority queue实现方法
#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_queuestruct 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";}
总结：
指针操作真是灰常烦。要格外小心！！！
