## [f]izzbuzzer

### Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

# Merge k sorted linked lists and return it as one sorted list

Sharing is caring!

Problem statement
Merge k sorted linked lists and return it as one sorted list.

Solution
We reduce the problem to the merging of two linked lists problem. This can be done in $\mathcal{O}(n)$ time and $\mathcal{O}(1)$ space. So we first write out the function to merge two sorted lists:

def merge(self, lst1, lst2):
if lst1 == None:
return lst2
if lst2 == None:
return lst1
if lst1.val < lst2.val:
lst1.next = self.merge(lst1.next, lst2)
return lst1
else:
lst2.next = self.merge(lst1, lst2.next)
return lst2


We can then go on and iterate over all the lists and merge them in pairs. We will merge the first two lists and then merge the resulting list with the subsequent list in the array. The use that result and merge it with the next un visited list and so on.

Full code

class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None

def __str__(self):
ans = ''
ans = ans + '->'

return ans

class Solution(object):
def merge(self, lst1, lst2):
if lst1 == None:
return lst2
if lst2 == None:
return lst1
if lst1.val < lst2.val:
lst1.next = self.merge(lst1.next, lst2)
return lst1
else:
lst2.next = self.merge(lst1, lst2.next)
return lst2

def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if len(lists) == 0:
return None

for i in range(0, len(lists) - 1):
lists[i+1] = self.merge(lists[i], lists[i+1])

return lists[-1]

def main():