Merge k Sorted Lists

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

Problem link


  • 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 {
    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){
        while (!q.empty()){
            min_node =;
            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;
Merge k Sorted Lists

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s