Merge K sorted list

You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.

Example 1:

`Input: lists = [[1,4,5],[1,3,4],[2,6]]Output: [1,1,2,3,4,4,5,6]Explanation: The linked-lists are:[  1->4->5,  1->3->4,  2->6]merging them into one sorted list:1->1->2->3->4->4->5->6`

Example 2:

`Input: lists = []Output: []`

Example 3:

`Input: lists = [[]]Output: []`

Constraints:

• `k == lists.length`

Approach 1:

K- pointer approach

This generalized problem of 2 pointer approach. In this problem we store the head pointer of each linked list in an array and for each time as we iterate through this head pointer array we find the least element in that iteration . And choose that least value as the next node of the resulting linked list. Also we update that head pointer in the array to its next value. Upon reaching end of any of the linked list, the entry for that linked list in the array is removed, by popping.

`class Solution:    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:        inter=[]        for i in lists:            if i!=None:                inter.append(i)        dummy=ListNode(0)        temp=dummy        while(inter):            i=0            mini_val=float('inf')            while(i<len(inter)):                if inter[i].val<=mini_val:                    mini_ind=i                    mini_val=inter[i].val                     i+=1                   temp.next=inter[mini_ind]            temp=temp.next            inter[mini_ind]=inter[mini_ind].next            if(inter[mini_ind]==None):                inter.pop(mini_ind)                        temp.next=None        return dummy.next`

Time:O(k*(n1+n2+n3+….+nk)), ni is the number of terms in each of the linked list

On assuming that every linked list have same number of elements “n”

Time complexity can be written as

= O(nk²)

Space:O(k) , k = number of linked lists

Approach 2 :

Using heap

We iterate through the entire array of linked list and then store the values to another array. Then create a min-heap with this new array by the heapify operation(Storing the elements first to the array and then heapifying rather than creating a min heap at first & then pushing the elements to it , reduces the complexity from O(n*klog(n*k)) to O(n*k)) .

Where k is the number of linked list and n is the size of each linked list on approximation.

Then we pop elements from this min heap and create the required sorted linked list.

`import heapq as hq class Solution:    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:        dummy=ListNode(0)        temp=dummy        heap=[]                for i in lists:            head=i            while(head):                heap.append(head.val)                head=head.next                        hq.heapify(heap)                while(heap):            temp.next=ListNode(hq.heappop(heap))            temp=temp.next        return dummy.next`

Time: O(n*k)

Space: O(n*k)

Tech-Enthusiast, Coder,Explorer,Geeky,Computer Science Engineering|A piece of code delivers everything that you need.

More from Dhanarajappu

Tech-Enthusiast, Coder,Explorer,Geeky,Computer Science Engineering|A piece of code delivers everything that you need.