# Merge k Sorted Lists

##### January 6, 2024

## Problem #

You are given an array of k linked lists, each containing nodes of sorted integers. Merge all the linked lists into one sorted linked list and return its head.

## Solution Approach #

**Divide:**Recursively divide the list of lists into two halves until each sublist contains only one or zero lists.**Conquer:**Merge each pair of sublists using a merge function that combines two sorted lists into a single sorted list.**Combine:**Recurse up the call stack, merging the results of the sub-problems until the final sorted list is obtained.

**Code (Python):**

```
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
"""
Merges k sorted linked lists into a single sorted linked list.
Args:
lists: A list of ListNode objects representing the sorted linked lists.
Returns:
The head of the merged sorted linked list.
"""
def mergeTwoLists(l1, l2):
"""Merges two sorted linked lists."""
dummy = tail = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 or l2
return dummy.next
if not lists:
return None # Handle empty input
# Recursively divide and merge lists
return mergeKLists(mergeTwoLists(lists[:len(lists) // 2], lists[len(lists) // 2:]))
```

### Time Complexity #

O(N log k), where N is the total number of nodes in all lists, and k is the number of lists.

### Space Complexity #

O(log k) for the recursion stack.