## Merge K sorted lists | Leetcode #23

This video explains a very important programming interview problem which is to merge K sorted lists.In this problem,we are given K lists in ascending order and we are required to merge all the K lists into a single list in ascending order and return the result.The given K lists can be in the form of array of vectors or linked lists etc.I have explained 5 different approaches to this problem using intuition and examples.The first technique is about merging the lists one by one.The second technique compares all the K candidate elements and selects the minimum.Both the techniques take O(NK) time.The third technique is about joining all the lists and applying merge sort.We can also do it by just copying the values.It takes O(NlogN) time.The fourth technique is based on Divide and Conquer technique which takes O(NlogK) time.The fifth technique is about heap which also takes O(NlogK) time.
The space complexity will be O(1) if we just manipulate pointers and merge the lists IN-PLACE without using any extra space, otherwise if we make a new linked list then that will be OUT OF PLACE algorithm which consumes extra space and so,space complexity in this case will be O(N).

## CODE: Divide & Conquer

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
//Divide_&_Conquer
class Solution {
ListNode *merge(vector<ListNode*>& lists,int left,int right)
{
if(left==right)     //Only 1 list,therefore can't be merged
return lists[left];

int k = right-left+1;   //No of current lists
head = h1 = h2 = NULL;
h1 = merge(lists,left,left+k/2-1);    //Merge 1st half and store its head in h1
h2 = merge(lists,left+k/2,right); //Merge 2nd half and store its head in h2

//Merge h1 and h2 into head
if(!h1 and !h2) //No list is present
else if(!h1)    //Only 2nd list is present
return h2;
else if(!h2)    //Only 1st list is present
return h1;

if(!h1 or (h1 and h1->val>h2->val))
{   head = h2;  h2=h2->next;    }
else
{   head = h1;  h1=h1->next;    }

while(h1 or h2)
{
if(!h1)
{   ptr->next = h2;   h2=h2->next;  ptr=ptr->next;  }
else if(!h2)
{   ptr->next = h1;   h1=h1->next;  ptr=ptr->next;  }
else if(h1->val < h2->val)
{   ptr->next=h1;   h1=h1->next;    ptr=ptr->next;  }
else
{   ptr->next=h2;   h2=h2->next;    ptr=ptr->next;  }
}
}
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int k = lists.size();
if(k==0)
return NULL;
else if(k==1)
return lists[0];
head = h1 = h2 = NULL;
h1 = merge(lists,0,k/2);    //Merge 1st half
if(k/2+1 <= k-1)
h2 = merge(lists,k/2+1,k-1);    //Merge 2nd half

//Merge h1 and h2 into head
if(!h1 and !h2) //No list is present
else if(!h1)    //Only 2nd list is present
return h2;
else if(!h2)    //Only 1st list is present
return h1;

if(!h1 or (h1 and h1->val>h2->val))
{   head = h2;  h2=h2->next;    }
else
{   head = h1;  h1=h1->next;    }

while(h1 or h2)
{
if(!h1)
{   ptr->next = h2;   h2=h2->next;  ptr=ptr->next;  }
else if(!h2)
{   ptr->next = h1;   h1=h1->next;  ptr=ptr->next;  }
else if(h1->val < h2->val)
{   ptr->next=h1;   h1=h1->next;    ptr=ptr->next;  }
else
{   ptr->next=h2;   h2=h2->next;    ptr=ptr->next;  }
}
}
};```

## CODE: Heap

```/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode() : val(0), next(nullptr) {}
*     ListNode(int x) : val(x), next(nullptr) {}
*     ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
struct node {
ListNode *curr;    //Current node
int idx;    //List index number
node(ListNode *a,int b)
{
curr = a;
idx = b;
}
};
struct compare {
bool operator()(node a, node b)
{
return a.curr->val >b.curr->val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
int k = lists.size();
if(k==0)
return NULL;
priority_queue<node,vector<node>,compare> heap;
vector<ListNode*> ptr(k);   //Current node ptrs for all the lists
//Assign all the current ptrs and BUILD_HEAP
for(int i=0;i<k;++i)
{
ptr[i]=lists[i];
if(ptr[i]!=NULL)
heap.push(node(ptr[i],i));
}

if(heap.empty())
return NULL;
//Insert 1st node
int idx = heap.top().idx;
heap.pop();
ptr[idx]=ptr[idx]->next;
if(ptr[idx])    //Push newly pointed node if not NULL
heap.push(node(ptr[idx],idx));

//Make list with rest of the nodes
while(!heap.empty())
{
ListNode *temp=heap.top().curr; //Pop root node
idx=heap.top().idx;
heap.pop();