leetcode-23 Merge k Sorted Lists

題意:合併k個已排序的linkedlist

解題思路:這題我是把全部的元素丟進c++ stl 的priority queue裡,能通過測試,但時間和空間複雜度太大,但我還是先貼我過的code,待我之後再刷到這時,再更新更快做法

效率更高做法: http://bangbingsyb.blogspot.tw/2014/11/leetcode-merge-k-sorted-lists.html

C++ code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    
public:
     struct cmp 
     { 
        bool operator()(ListNode* x,ListNode*  y) 
        { 
            return x->val > y->val; 
        } 
     }; 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        int len=lists.size();
        
        for(int i=0;i<len;i++)
        {
            ListNode* par=lists[i]; 
            while(par!=NULL)
            {
                pq.push(par);
                par=par->next;
            }
        }
        ListNode* ori=new ListNode(0);
        ListNode* cur=ori;
        while(!pq.empty())
        {
            cur->next=pq.top();
            pq.pop();
            cur=cur->next;
            
        }
        cur->next=NULL;
        return ori->next;
    }
};