Merge K Sorted Linked Lists

Problem Statement

You are given an array of k linked lists lists, where each list is sorted in ascending order.

Return the sorted linked list that is the result of merging all of the individual linked lists.

Example 1:

Input: lists = [[1,2,4],[1,3,5],[3,6]]
Output: [1,1,2,3,3,4,5,6]

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

  • 0 <= lists.length <= 1000
  • 0 <= lists[i].length <= 100
  • -1000 <= lists[i][j] <= 1000

You should aim for a solution as good or better than O(n * k) time and O(1) space, where k is the total number of lists and n is the total number of nodes across all lists.

You should aim for a solution as good or better than O(n * k) time and O(1) space, where k is the total number of lists and n is the total number of nodes across all lists.

Hint 1

A brute-force solution would involve storing all n nodes in an array, sorting them, and converting the array back into a linked list, resulting in an O(nlogn) time complexity. Can you think of a better way? Perhaps consider leveraging the idea behind merging two sorted linked lists.

Hint 2

We can merge two sorted linked lists without using any extra space. To handle k sorted linked lists, we can iteratively merge each linked list with a resultant merged list. How can you implement this?

Hint 3

We iterate through the list array with index i, starting at i = 1. We merge the linked lists using merge_two_lists(lists[i], lists[i - 1]), which returns the head of the merged list. This head is stored in lists[i], and the process continues. Finally, the merged list is obtained at the last index, and we return its head.

Solution

Brute Force

# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
nodes = []
for lst in lists:
while lst:
nodes.append(lst.val)
lst = lst.next
nodes.sort()
res = ListNode(0)
cur = res
for node in nodes:
cur.next = ListNode(node)
cur = cur.next
return res.next

Time complexity: O(n log n) Space complexity: O(n)

Iteration

# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
res = ListNode(0)
cur = res
while True:
min_node = -1
for i in range(len(lists)):
if not lists[i]:
continue
if min_node == -1 or lists[min_node].val > lists[i].val:
min_node = i
if min_node == -1:
break
cur.next = lists[min_node]
lists[min_node] = lists[min_node].next
cur = cur.next
return res.next

Time complexity: O(n * k) Space complexity: O(1)

Merge Lists One By One

# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if len(lists) == 0:
return None
for i in range(1, len(lists)):
lists[i] = merge_list(lists[i - 1], lists[i])
return lists[-1]
def merge_list(l1, l2):
dummy = ListNode()
tail = dummy
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
if l1:
tail.next = l1
if l2:
tail.next = l2
return dummy.next

Time complexity: O(n * k) Space complexity: O(1)

Heap

import heapq
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class NodeWrapper:
def __init__(self, node):
self.node = node
def __lt__(self, other):
return self.node.val < other.node.val
def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if len(lists) == 0:
return None
res = ListNode(0)
cur = res
min_heap = []
for lst in lists:
if lst is not None:
heapq.heappush(min_heap, NodeWrapper(lst))
while min_heap:
node_wrapper = heapq.heappop(min_heap)
cur.next = node_wrapper.node
cur = cur.next
if node_wrapper.node.next:
heapq.heappush(min_heap, NodeWrapper(node_wrapper.node.next))
return res.next

Time complexity: O(n log k) Space complexity: O(k)

Divide And Conquer (Recursion)

# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_k_lists(lists):
if not lists or len(lists) == 0:
return None
return divide(lists, 0, len(lists) - 1)
def divide(lists, l, r):
if l > r:
return None
if l == r:
return lists[l]
mid = l + (r - l) // 2
left = divide(lists, l, mid)
right = divide(lists, mid + 1, r)
return conquer(left, right)
def conquer(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
if l1:
curr.next = l1
else:
curr.next = l2
return dummy.next

Time complexity: O(n log k) Space complexity: O(log k)

Divide And Conquer (Iteration)

# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_k_lists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists or len(lists) == 0:
return None
while len(lists) > 1:
merged_lists = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i + 1] if (i + 1) < len(lists) else None
merged_lists.append(merge_list(l1, l2))
lists = merged_lists
return lists[0]
def merge_list(l1, l2):
dummy = ListNode()
tail = dummy
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
if l1:
tail.next = l1
if l2:
tail.next = l2
return dummy.next

Time complexity: O(n log k) Space complexity: O(k)