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;
    }
};