# Simple C++ solution using heaps O(n*logk)

• It's pretty straightforward. Maintain a heap of size K, everytime we pop off the min element, then push it's next element on the heap if it's not null. Maintain a curr pointer so we can link all the nodes together, as well as a head pointer for the first pop.

``````class Solution {
public:
struct NodeCmp {
bool operator()(ListNode *a, ListNode *b) {
return a->val > b->val;
}
};

ListNode *mergeKLists(vector<ListNode *> &lists) {
vector<ListNode*> heap;
// make heap with the first element of each list
for(int i = 0; i < lists.size(); ++i) {
if (lists[i] != NULL) {
heap.push_back(lists[i]);
}
}
make_heap(heap.begin(), heap.end(), NodeCmp());

ListNode *curr = NULL;
while(!heap.empty()) {
ListNode *min = heap.front();
pop_heap(heap.begin(), heap.end(), NodeCmp());
heap.pop_back();

if(curr)
curr->next = min;
curr = min;
// add next element from list to heap if it's not null
if(curr->next) {
heap.push_back(curr->next);
push_heap(heap.begin(), heap.end(), NodeCmp());
}
}
}
};``````

• you know lambda function can also be used:
auto comp = [](pair<ListNode*, int> p1, pair<ListNode*, int> p2){
return p1.first->val > p2.first->val;
};

• This post is deleted!

• /**

• struct ListNode {

• ``````int val;
``````
• ``````ListNode *next;
``````
• ``````ListNode(int x) : val(x), next(NULL) {}
``````
• };
/
class Solution {
public:
class MyNode
{
public:
ListNode
pNode;
int listId;
};
class Comparer
{
public:
bool operator() (MyNode& p1, MyNode& p2)
{
return p1.pNode->val > p2.pNode->val;
}
};
ListNode *mergeKLists(vector<ListNode *> &lists) {

`````` ListNode* pPrev = NULL;
ListNode* pRet = NULL;

priority_queue<MyNode, vector<MyNode>,Comparer> min_heap;

for (int i =0; i< lists.size(); i++)
{
if (lists[i])
{
MyNode obj;
obj.pNode = lists[i];
obj.listId = i;
min_heap.push(obj);
lists[i] = lists[i]->next;
}
}

while(min_heap.size())
{

MyNode Curr = min_heap.top();
min_heap.pop();

if (lists[Curr.listId])
{
MyNode obj;
obj.pNode = lists[Curr.listId];
obj.listId = Curr.listId;
min_heap.push(obj);
lists[Curr.listId] = lists[Curr.listId]->next;
}

if (pPrev)
pPrev->next = Curr.pNode;
else
pPrev = pRet = Curr.pNode;

pPrev = Curr.pNode;

}
if (pPrev)
pPrev->next = NULL;

return pRet;
``````

}
};

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