
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
/** * Definition for singly-linked list. * 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 ListNode *head,*h1,*h2,*ptr; 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 return head; 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; } ptr = head; 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; } } return head; } public: ListNode* mergeKLists(vector<ListNode*>& lists) { int k = lists.size(); if(k==0) return NULL; else if(k==1) return lists[0]; ListNode *head,*h1,*h2,*ptr; 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 return head; 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; } ptr = head; 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; } } return head; } };
CODE: Heap
/** * Definition for singly-linked list. * 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; ListNode *head,*tail; head=tail=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 head=tail=heap.top().curr; 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(); tail->next=temp; //Add newnode to list tail=tail->next; ptr[idx]=ptr[idx]->next; //Update current pointer if(ptr[idx]) //Push newly pointed node if not NULL heap.push(node(ptr[idx],idx)); } return head; } };