Merge K Sorted Lists

来源：Leetcode

原帖：http://oj.leetcode.com/problems/merge-k-sorted-lists/

题目：
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
    
 class compare {  
 public:  
     bool operator() (ListNode* left, ListNode* right) { // min-heap  
         return left->val > right->val;  
     }  
 };  
   
 class Solution {  
 public:  
     ListNode *mergeKLists(vector<ListNode *> &lists) {  
         if (lists.empty()) return NULL;      
         priority_queue<ListNode*, vector<ListNode*>, compare> heap;  
         for (int i = 0; i < lists.size(); i++) {  
             if (lists[i]) {  
                 heap.push(lists[i]);  
             }  
         }  
         ListNode dummy(0);  
         ListNode* tail = &dummy;  
         while(!heap.empty()) {  
             tail->next = heap.top();   
             heap.pop();  
             tail = tail->next;  
             if(tail->next) {  
                 heap.push(tail->next);  
             }  
         }  
         return dummy.next;  
     }  
 };