# 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)