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.
Recommended Time and Space Complexity
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)