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";  
}  

 

 

补充：软件开发 , C++ ,