Merge K Sorted Lists
Problem
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.
Examples
Example 1:
graph TB classDef darkMode fill:transparent,stroke:#ff8c00,stroke-width:2px,font-weight:bold,font-size:14px; subgraph In[" "] L1(1):::darkMode --> L2(4):::darkMode --> L3(5):::darkMode L4(1):::darkMode --> L5(3):::darkMode --> L6(4):::darkMode L7(2):::darkMode --> L8(6):::darkMode end subgraph Out[" "] A(1):::darkMode --> B(1):::darkMode --> C(2):::darkMode --> D(3):::darkMode --> E(4):::darkMode --> F(4):::darkMode --> G(5):::darkMode --> H(6):::darkMode end In -->|"Merge"| Out linkStyle default stroke:#ff8c00,stroke-width:2px;
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Similar Problems
[Merge 2 Sorted Linked Lists](merge-two-sorted-linked-lists)
Solution
This problem is marked hard, depending on how we solve this problem. This is
Video explanation
Here is the video explaining below methods in detail. Please check it out:
<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/0toMyveldys" frameborder="0" allowfullscreen></iframe></div>
Method 1 - Using merge 2 lists solution sequentially
We have already solved [Merge Two Sorted Lists](merge-two-sorted-linked-lists). The naive approach involves merging the k sorted linked lists by iteratively merging two lists at a time. This approach is simple but less efficient compared to the optimal solution. Here’s how it works:
- Sequentially Merge Two Lists at a Time:
- Start with the first two linked lists.
- Merge them into a single sorted list.
- Continue merging the result with the next linked list, until all
klists are merged.
- Merge Two Sorted Lists:
- Use the technique for merging two sorted linked lists.
- Compare the values at the current nodes of both lists, and append the smaller node to the result list.
- Move to the next node in the list that contributed the smaller node.
- Repeat until both lists are fully merged.
Code
Java
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode ans = null;
for (ListNode l : lists) {
ans = mergeTwoLists(ans, l);
}
return ans;
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode ans = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
ans.next = l1;
l1 = l1.next;
} else {
ans.next = l2;
l2 = l2.next;
}
ans = ans.next;
}
ans.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
Python
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(-1)
ans = dummy
while l1 and l2:
if l1.val < l2.val:
ans.next = l1
l1 = l1.next
else:
ans.next = l2
l2 = l2.next
ans = ans.next
ans.next = l1 if l1 else l2
return dummy.next
ans = None
for l in lists:
ans = mergeTwoLists(ans, l)
return ans
Complexity
- ⏰ Time complexity:
O(n*k). Each merge operation takesO(n)wherenis the total number of nodes across all linked lists. Mergingklinked lists sequentially results in:O(nk)This is due tok - 1merge operations. - 🧺 Space complexity:
O(1). This approach uses no additional data structures apart from the output linked list nodes.
Method 2 - Using Merge sort Divide and Conquer (recursive)
This is similar to [Merge Sort Algorithm#Method 1 - Recursive Top Down Merge Sort](merge-sort-algorithm.md/#method-1---recursive-top-down-merge-sort) solution, resembling method 3's iterative approach.
Code
Java
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
return mergeSort(lists, 0, lists.length - 1);
}
private ListNode mergeSort(ListNode[] lists, int start, int end) {
if (start == end) {
return lists[start];
}
if (start > end) {
return null;
}
int mid = (start + end) / 2;
ListNode left = mergeSort(lists, start, mid);
ListNode right = mergeSort(lists, mid + 1, end);
return mergeTwoLists(left, right);
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode ans = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
ans.next = l1;
l1 = l1.next;
} else {
ans.next = l2;
l2 = l2.next;
}
ans = ans.next;
}
ans.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
Python
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def mergeTwoLists(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(-1)
ans = dummy
while l1 and l2:
if l1.val < l2.val:
ans.next = l1
l1 = l1.next
else:
ans.next = l2
l2 = l2.next
ans = ans.next
ans.next = l1 if l1 else l2
return dummy.next
def mergeSort(lists: List[Optional[ListNode]], start: int, end: int) -> Optional[ListNode]:
if start == end:
return lists[start]
if start > end:
return None
mid = (start + end) // 2
left = mergeSort(lists, start, mid)
right = mergeSort(lists, mid + 1, end)
return mergeTwoLists(left, right)
return mergeSort(lists, 0, len(lists) - 1)
Complexity
- ⏰ Time complexity:
O(n log k) - 🧺 Space complexity:
O(k)
Method 3 - Using merge 2 lists solution in a merge sort way
We have already solved [Merge Two Sorted Linked Lists](merge-two-sorted-linked-lists), that merges 2 sorted lists. We can also club [Merge Sort Algorithm#Method 2 - Iterative or Bottom up Merge Sort](merge-sort-algorithm.md/#method-2---iterative-or-bottom-up-merge-sort).
So, we will keep on merging 2 lists at a time, till we have 1 list remaining.
So, initially we will have k/2 lists remaining, then k/4 and finally after some time 1 remaining.
We take O(n) time to merging 2 sorted lists, finally we have time complexity of O(n * log k).
T(N) = 2 T(K/2) + N
T(N) = O (N log K)
Code
Java
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0)
return null;
int k = lists.length;
while(k>=1){
// pick 1 list from start, another for end.
for(int i = 0; i < k/2; i++){
ListNode l1 = lists[i];
ListNode l2 = lists[k-i-1];
lists[i] = mergeTwoLists(l1, l2);
}
// we have to now process remaining k/2 list
k = k /2;
}
return lists[0];
}
Above solution has issues, so rewriting:
public ListNode mergeKLists(ListNode[] lists) {
if(lists==null || lists.length==0) return null;
for(int step = 1; step < lists.length; step <<= 1) {
for(int i = 0; i < lists.length-step; i += 2*step)
lists[i] = mergeTwoLists(lists[i], lists[i+step]);
}
return lists[0];
}
Complexity
- ⏰ Time complexity:
O(n log k) - 🧺 Space complexity:
O(1)
Cons: Does in place modification.
Method 4 - Using Min Heap
We should add heads of all k sorted lists. At every instant, you need the minimum of the head of all the k linked list. Once you know the minimum, you can push the node to your answer list, and move over to the next node in that linked list.
The simplest solution is using PriorityQueue as min heap. The elements of the priority queue are ordered according to their natural ordering, or by a comparator provided at the construction time (in this case).
Code
Java
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
(a, b) -> Integer.compare(a.val, b.val) // Compare nodes by their value
);
// Add the head nodes of all lists to the priority queue
for (ListNode head : lists) {
if (head != null) {
minHeap.add(head);
}
}
ListNode dummy = new ListNode(-1);
ListNode ans = dummy;
while (!minHeap.isEmpty()) {
// Extract the smallest node
ListNode node = minHeap.poll();
ans.next = node;
ans = ans.next;
// If the node has a next element, add it to the heap
if (node.next != null) {
minHeap.add(node.next);
}
}
return dummy.next;
}
}
Python
class Solution:
def mergeKLists(self, lists: List[Optional['ListNode']]) -> Optional['ListNode']:
# Create a min-heap
min_heap: List[Tuple[int, int, ListNode]] = []
# Add the head nodes of all linked lists to the heap (value, index, node)
for i, head in enumerate(lists):
if head:
heapq.heappush(min_heap, (head.val, i, head))
dummy = ListNode(-1)
ans = dummy
while min_heap:
# Extract the smallest node (value, index, node)
_, i, node = heapq.heappop(min_heap)
ans.next = node
ans = ans.next
# If the extracted node has a next node, insert its next node into the heap
if node.next:
heapq.heappush(min_heap, (node.next.val, i, node.next))
return dummy.next
Complexity
- ⏰ Time complexity:
O(log(k) * n), k is number of list and n is number of total elements. - 🧺 Space complexity:
O(k)