Merge k Sorted Lists

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

Problem link

Solution

  • using a priority queue to keep the organize the k current candidates
  • note that the default priority_queue in cpp is max_heap, I need to implement my own comparator function that supports min_heap with pointers as elements
struct compNode {
bool operator()(ListNode *p, ListNode *q) const {
            return p->val>q->val;
        }  
    };

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, compNode> q;
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        ListNode* min_node;
        for (auto n:lists){
            if (n){
                q.push(n);
            }
        }
        while (!q.empty()){
            min_node = q.top();
            q.pop();
            cur -> next = min_node;
            cur = cur->next;
            min_node = min_node->next;
            if (min_node) q.push(min_node);
        }
        cur -> next = NULL;
        cur = dummy->next;
        delete (dummy);
        return cur;
    }
};
Advertisements
Merge k Sorted Lists

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s