Priority Queue based solution

• ``````class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {

PriorityQueue pq(&lists);
if(pq.Build())
{
List l;
int val;
bool first = true;
bool keepOn = true;

while(keepOn)
{
keepOn = pq.GetMin(val);
PushBack(l, val);
if(first)
{
first = false;
}
}

}
else
return NULL;
}

struct List
{
ListNode * tail;
};

void PushBack(List& l, int val)
{
ListNode * ntail = new ListNode(val);
if(l.tail)
l.tail->next = ntail;
l.tail = ntail;
}

struct PriorityQueue{

PriorityQueue(vector<ListNode*>* v) : m_Container(v), m_NumLists(v->size())
{
}

int Parent(int i){ assert(i>0); return ((i+1)/2 - 1);}
int Left(int i){ return (2*(i+1)-1);}
int Right(int i){ return (2*(i+1));}

void MinHeapify(int i)
{
int l = Left(i);
int r = Right(i);
int minIdx;

if(l < m_NumLists && (*m_Container)[l] && (*m_Container)[l]->val < (*m_Container)[i]->val)
minIdx = l;
else
minIdx = i;

if(r < m_NumLists && (*m_Container)[r] && (*m_Container)[r]->val < (*m_Container)[minIdx]->val)
minIdx = r;

if(minIdx != i)
{
ListNode * tmp = (*m_Container)[i];
(*m_Container)[i] = (*m_Container)[minIdx];
(*m_Container)[minIdx] = tmp;
MinHeapify(minIdx);
}
}

bool Build()
{
auto cit = remove_if(m_Container->begin(), m_Container->end(),
[](ListNode * tmp)->bool{
return tmp == NULL;
});

m_Container->erase(cit, m_Container->end());
m_NumLists = m_Container->size();

if(m_Container->size() > 0)
{
for(int i = m_Container->size()/2; i>=0; i--)
MinHeapify(i);
return true;
}
else
return false;
}

bool GetMin(int& val)
{
val = (*m_Container)[0]->val;

ListNode * tmp = (*m_Container)[0]->next;
delete (*m_Container)[0];
(*m_Container)[0] = tmp;

if(tmp)
{
MinHeapify(0);
return true;
}
else
{
if(m_NumLists > 1)
{
swap((*m_Container)[0], (*m_Container)[m_NumLists-1]);
m_NumLists--;
MinHeapify(0);
return true;
}
else
return false;
}
}

vector<ListNode *>* m_Container;
int m_NumLists;
};

};``````

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