Merge K Sorted Lists

We are given a list containing K number of Sorted Linked List. Need to merge them altogether and return a new sorted linked list.

This problem is an extension of Merge Two Sorted Lists problem. Solve that problem first, because we are not going go deep into how to Merge Two Sorted Lists, so that one is prerequisite. Let's start building the intuition first. Assume we have 4 linked lists as bellow

We will take each pair of lists and merge them using our existing solution for mergeTwoSortedLists like this bellow.

We will keep doing this until the Lists contains only one sorted Linked List.

# Definition for singly-linked list.
# class ListNode:
	# def __init__(self, val=0, next=None):
	# self.val = val
	# self.next = next

class Solution:
	def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
		# Handling edge cases first
		if not lists:
			return None
		# Keep merged until the given list has only one merged Linked List
		while len(lists) > 1:
			merged_lists = []  # will save the merged pairs here
			for i in range(0, len(lists), 2):
				list1 = lists[i]
				# handle index out of bound error
				list2 = lists[i+1] if (len(lists) > i+1) else None
				merged_list = self.mergeTwoSortedList(list1, list2)
				merged_lists.append(merged_list)
			
			# at this point all the small lists are merged.
			# overwriting lists with the computed result
			lists = merged_list
		return lists[0]

Here we skipped the implementation of mergeTwoSortedList. Let's align our thoughts with the given example.

That's it for today. Thanks for stopping by!

Connect with me on