# My solution based on priority_queue (with some questions)

• The general idea of this problem to find the node with the least value and append to one linked list.
But how to find the minimal value quickly? I use a priority queue (heap) the save all the head node of lists (which is not null).
So the top of the heap is the minimal node, then append it to the result linked list and push the `node->next` into the heap, until the heap is empty.

But the heap cannot save `ListNode *`. I have to `new ListNode()` to append node to linked list, which may waste memory. How can I solve it?

Thanks

``````// reload the operator to make the min heap
bool operator< (ListNode a, ListNode b){
return a.val > b.val;
};

class Solution {
public:

ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode> q;
for (vector<ListNode *>::iterator it = lists.begin(); it != lists.end(); ++it) {
if (*it != NULL) {
q.push(**it);  // push heads of lists
}
}
while (!q.empty()) {
ListNode n = q.top();
q.pop();
p->next = new ListNode(n.val);
p = p->next;
if (n.next != NULL) {
q.push(*(n.next));
}
}