Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6

# Merge two list

This problem rings a bell about a simpler version of the problem: merge 2 lists. We might need to use it later.

```
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
new_dummy_head = ListNode(1)
cur_ptr = new_dummy_head
while l1 and l2:
if l1.val < l2.val:
cur_ptr.next = l1
l1 = l1.next
else:
cur_ptr.next = l2
l2 = l2.next
cur_ptr = cur_ptr.next
if not l1:
cur_ptr.next = l2
if not l2:
cur_ptr.next = l1
return new_dummy_head.next
```

# Combine one by one

We will call mergeTwoList k – 1 times and return the head.

```
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if not lists:
return None
if len(lists) == 1:
return lists[0]
dummy_head = lists[0]
for i in range(1, len(lists)):
dummy_head = self.mergeTwoLists(dummy_head, lists[i])
return dummy_head
```

## Space complexity

Since mergeTwoLists only alter next pointers of node, the space complexity is O(1).

## Time complexity

Let the number of total node be N and the number of linked list be k.

We need to call mergeTwoList k – 1 times. And in the worst case, we need to traverse over the longer linked list of the two. Assuming the length of each linked list is equal, the longer linked list will have length of n / k, 2n / k … (k – 1)n/k. So the run time is

# Divide and conquer

Divide and conquer is a problem solving patterns that combine solutions of smaller instance to find the solution of the bigger problem.

In this problem, merge k linked list can become merging k // 2 linked lists who are the result of merging pairs of linked list.

def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if not lists:
return None
if len(lists) == 1:
return lists[0]
head_1 = self.mergeKLists(lists[:len(lists) // 2])
head_2 = self.mergeKLists(lists[len(lists) // 2:])
h = self.mergeTwoLists(head_1, head_2)
return h

## Run time

We have k linked list, so we will merge at most logk times. In the worst case scenario, the length of the longer linked list is O(n). So The run time is O(n log k).