[LeetCode]Merge k Sorted Lists

[cpp] 
struct ListNode { 
    int val; 
    ListNode *next; 
    ListNode(int x) : val(x), next(NULL) {} 
}; 
 
class Solution { 
//O(nlogk)  
//using priority_queue to choose current minimum node  
//node: keep priority_queue free of NULL pointer  
public: 
    struct PQNode 
    { 
        int index; 
        ListNode* ptr; 
        PQNode(int _index = 0, ListNode* _ptr = NULL):index(_index),ptr(_ptr){} 
    }; 
    struct Comp 
    { 
        bool operator()(const PQNode& lhs, const PQNode& rhs) const 
        { 
            return lhs.ptr->val > rhs.ptr->val; 
        } 
    }; 
    ListNode *mergeKLists(vector<ListNode *> &lists) { 
        // Start typing your C/C++ solution below  
        // DO NOT write int main() function  
        priority_queue<PQNode, vector<PQNode>, Comp> pq; 
        ListNode* head = NULL; 
        ListNode* cur = NULL; 
        do 
        { 
            for(int i = 0; i < lists.size(); ++i) 
            { 
                if(lists[i] != NULL) 
                { 
                    pq.push(PQNode(i, lists[i])); 
                    lists[i] = lists[i]->next; 
                } 
            } 
            if(pq.empty()) break; 
            if(head == NULL) 
                head = pq.top().ptr; 
            else  
                cur->next = pq.top().ptr; 
            cur = pq.top().ptr; 
            int curIdx = pq.top().index; 
            pq.pop(); 
            if(lists[curIdx] != NULL) 
            { 
                pq.push(PQNode(curIdx, lists[curIdx])); 
                lists[curIdx] = lists[curIdx]->next; 
            } 
        }while(true); 
        if(cur != NULL) cur->next = NULL; 
        return head; 
    } 
}; 

struct ListNode {
 int val;
 ListNode *next;
 ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
//O(nlogk)
//using priority_queue to choose current minimum node
//node: keep priority_queue free of NULL pointer
public:
 struct PQNode
 {
  int index;
  ListNode* ptr;
  PQNode(int _index = 0, ListNode* _ptr = NULL):index(_index),ptr(_ptr){}
 };
 struct Comp
 {
  bool operator()(const PQNode& lhs, const PQNode& rhs) const
  {
   return lhs.ptr->val > rhs.ptr->val;
  }
 };
 ListNode *mergeKLists(vector<ListNode *> &lists) {
  // Start typing your C/C++ solution below
  // DO NOT write int main() function
  priority_queue<PQNode, vector<PQNode>, Comp> pq;
  ListNode* head = NULL;
  ListNode* cur = NULL;
  do
  {
   for(int i = 0; i < lists.size(); ++i)
   {
    if(lists[i] != NULL)
    {
     pq.push(PQNode(i, lists[i]));
     lists[i] = lists[i]->next;
    }
   }
   if(pq.empty()) break;
   if(head == NULL)
    head = pq.top().ptr;
   else
    cur->next = pq.top().ptr;
   cur = pq.top().ptr;
   int curIdx = pq.top().index;
   pq.pop();
   if(lists[curIdx] != NULL)
   {
    pq.push(PQNode(curIdx, lists[curIdx]));
    lists[curIdx] = lists[curIdx]->next;
   }
  }while(true);
  if(cur != NULL) cur->next = NULL;
  return head;
 }
};