Online Judge Solutions

Thursday, December 25, 2014

Merge k Sorted Lists

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

 
/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
 
struct myComparor
{
  bool operator()(ListNode *lhs, ListNode *rhs) const
  {
     return lhs->val > rhs->val;
  }
};

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode *, vector<ListNode *>, myComparor > minHeap;
        for(ListNode *node : lists) {
            if (node)
               minHeap.push(node);
        }
        
        ListNode dummy(0);
        
        ListNode *p = &dummy;
        while(minHeap.size() > 0) {
            p->next = minHeap.top();
            minHeap.pop();
            p = p->next;
            if (p->next) 
              minHeap.push(p->next);
            // p->next = NULL; // this line was not necessary
        }
        
        return dummy.next;
    }
};

No comments:

Post a Comment