Merge K sorted list

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

Merge all the linked-lists into one sorted linked-list and return it.

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
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length won't exceed 10^4.

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)