Problem Statement:

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.

Questions

• What is the length of lists?

Solution #1: Divide & Conquer w/ Queue

When solving this question, it is obvious we should merge two lists at a time with respect to the k amount of lists. But if we combined one sorted list with another sorted list one by one each time, that is a lot of repeated work we are doing sorting. But instead, we can divide and conquer this problem, by pairing up lists and merging each pair, and after each pairing is done, the lists are merged and halved in length each time. We can repeat this until we only have 1 linked list left.

class ListNode:
		def __init__(self, val=0, next=None):
				self.val = val
				self.next = next
				
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
		if len(lists) == 0:
				return None
				
		queue = deque(lists)
		
		while len(queue) > 1:
				firstList = queue.popleft()
				secondList = queue.popleft()
				node = ListNode(0)
				head = node
				while firstList and secondList:
						if firstList.val < secondList.val:
								node.next = firstList
								firstList = firstList.next
						else:
								node.next = secondList
								secondList = secondList.next
						node = node.next
				
				if firstList:
						node.next = firstList
				if secondList:
						node.next = secondList
						
				queue.append(head.next)
				
		return queue.popleft()

Time Complexity: O(nlogk)

Where n is the total number of nodes in two given lists. And since we are halving the size of the queue each time, we are running the problem in logk time. If we instead demonstrated the lengths of two lists as a and b, we could say for every iteration of two lists, we are iterating and merging them over a runtime of a + b, so you could write it as O ( (a + b) * logk)

Space Complexity: O(k)

Where k is the number of lists in the queue.

Solution #2: Divide & Conquer Constant Space

We can solve this in constant space as well, using a for loop and an interval factor. Since we know the list will be halved each time, first becoming k/2, then k/4, k/8, k/16 and so on, we see that the factor on which lists decreases in length is 2, so we can merge the lists in each interval position by this factor, on every iteration we do.

class ListNode:
		def __init__(self, val=0, next=None):
				self.val = val
				self.next = next
				
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
		if len(lists) == 0:
				return None
				
		amount = len(lists)
		interval = 1
		
		while interval < amount:
				for i in range(0, amount - interval, interval * 2):
						lists[i] = self.merge2Lists(lists[i], lists[i + interval])
				interval *= 2
				
		return lists[0] if amount > 0 else None
		
def merge2Lists(self, l1, l2):
		head = point = ListNode(0)
		while l1 and l2:
				if l1.val <= l2.val:
						point.next = l1
						l1 = l1.next
				else:
						point.next = l2
						l2 = l2.next
				point = point.next
				
		if l1:
				point.next = l1
		if l2:
				point.next = l2
				
		return head.next

Time Complexity: O(nlogk)

Same as above.

Space Complexity: O(1)

Now using constant space since we merge the list values in place.