# Brief C++ solution with priority_queue

• We just need to define a comparison struct for ListNodes, then managing the priority_queue is quite straightforward. After filling the priority_queue, if it is non-empty, we set the head and tail. Then we repeatedly pop the top off the queue and append that to the tail. If the next node is not null, we push it onto the queue.

``````class Solution {
struct compare {
bool operator()(const ListNode* l, const ListNode* r) {
return l->val > r->val;
}
};

public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode *, vector<ListNode *>, compare> q;
for (auto l : lists) {
if (l) {
q.push(l);
}
}

if (q.empty()) {
return NULL;
}

ListNode* result = q.top();
q.pop();
if (result->next) {
q.push(result->next);
}

ListNode* tail = result;
while (!q.empty()) {
tail->next = q.top();
q.pop();
tail = tail->next;
if (tail->next) {
q.push(tail->next);
}
}

return result;
}
};``````

• little refine to make it shorter :)

``````ListNode *mergeKLists(vector<ListNode *> &lists) {
std::priority_queue<ListNode*, std::vector<ListNode*>, mycomparison > heap;
int i, k, n = lists.size();
for (i = 0; i < n; i++)
if (lists[i]) heap.push(lists[i]);
while (!heap.empty()){
curNode->next = heap.top();
heap.pop();
curNode = curNode->next;
if (curNode->next) heap.push(curNode->next);
}
}``````

• Nice. The trick of constructing a helper head node makes a lot of linked list algorithms much simpler.

• It's close to my solution. But I found using priority_queue is quite slow and my runtime is 430ms.

• Until I see the first answer written by cfjmonkey, I'm confused with `heap` and `priority_queue` version solution of this problem. Rewrite it by using `make_heap`. Now it's easy to see the difference.

``````ListNode* mergeKLists(vector<ListNode*>& lists) { //make_heap
vector<ListNode*> v;
for(int i =0; i<lists.size(); i++){
if (lists[i]) v.push_back(lists[i]);
}
make_heap(v.begin(), v.end(), heapComp); //vector -> heap data strcture

while(v.size()>0){
curNode->next=v.front();
pop_heap(v.begin(), v.end(), heapComp); v.pop_back();
curNode = curNode->next;
if(curNode->next) {
v.push_back(curNode->next);
push_heap(v.begin(), v.end(), heapComp);
}
}
}
static bool heapComp(ListNode* a, ListNode* b) {
return a->val > b->val;
}``````

• Dude, you are alive! @ChiangKaiShrek

• Nice implementation .
Here are some example how to use the compare-component-function

-Method 1 -

``````       std::priority_queue<int, std::vector<int>, decltype(&compare)> pq(&compare);
``````

The compare can be any your defined function

-Method 2-

You can use the default less function

``````     std::priority_queue<int, std::vector<int>, std::less<int> > pq;
``````

-Method 3-

You can use the lamda-expression

``````   auto comp = [] (int &a, int &b) -> bool { return a < b; };
std::priority_queue<int,std::vector<int>, decltype(comp) > pq (comp);``````

• the default `comp` is `less<T>`, why compare is `l->val > r->val` instead of `l->val < r->val`

• use a dummy node so you don't have to one extra iteration outside of while loop.

• ``````class Solution {
struct compare {
bool operator()(const ListNode* l, const ListNode* r) {
return l->val > r->val;
}
};

public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode *, vector<ListNode *>, compare> q;
for (auto l : lists)
if (l)
q.push(l);

ListNode* dummy = new ListNode(0);
ListNode* tail=dummy;
while (!q.empty()) {
tail->next = q.top();
q.pop();
tail = tail->next;
if (tail->next) {
q.push(tail->next);
}
}

return dummy->next;
}
};``````

• you forget to `delete dummy` before return...

``````bool operator()(const ListNode* & l, const ListNode* & r) {
return l->val > r->val;
}
``````

why I cannot add & ?

• @meow- I think that is probably because you try to insert every element into priority queue first. If you only insert the first element of every lists and call top() and pop() of priority queue, it is pretty fast.

• @needforspeed did you get the reason behind this ?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.