• Tweet

• Tweet

leetcode – Merge k Sorted Lists and return it as one sorted list. 

struct ListNode {

int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

Solution 1:

ListNode *mergeKLists(vector<ListNode *> &lists) {

ListNode *head=NULL,*res = NULL;

int min=INT_MAX,pos=-1,count=0;
for(int i=0 ; i < lists.size() ; i++)
{
if(lists[i] !=NULL && lists[i]->val < min)
{
pos=i;
min=lists[i]->val;
}
if(i==(lists.size()-1) )
{
if(pos == -1)
break;
if(res==NULL)
{
res=new ListNode(lists[pos]->val);
head=res;
}
else
{
res->next=new ListNode(lists[pos]->val);
res=res->next;
}
lists[pos]=lists[pos]->next;
if(lists[pos] ==NULL)
count ++;
if(count== lists.size())
break;
i=-1;
min=INT_MAX;
pos=-1;
}
}
return head;

}

Solution 2: A better approach

ListNode *mergeKLists(vector<ListNode *> &lists) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode* head=new ListNode(0);
if (lists.size()==0){return NULL;}
head->next = lists[0];
ListNode *p;
ListNode *q;
for (int i=1;i<lists.size();i++){
p = head;
q = lists[i];
while (q){
if (!p->next){
p->next = q;
break;
}
if (p->next->val<q->val){
p=p->next;
}else{
ListNode *l = p->next;
p->next = q;
q=q->next;
p->next->next =l;
p=p->next;
}
}
}
return head->next;
}

Solution 3 : using priority queue – Further improvement

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

ListNode *mergeKLists(vector<ListNode *> &lists) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
priority_queue<ListNode*, vector<ListNode*>, Compare> q;

for (auto p: lists ) {
if (p != NULL )
q.push( p );
}

if (q.empty()) return NULL;

ListNode* head = NULL;
head = q.top();
q.pop();
if (head->next) q.push(head->next);

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