23. Merge k Sorted Lists
Merge k Sorted Lists
Problem Description
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.
Example 1:
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
Example 2:
Input: lists = [] Output: []
Example 3:
Input: lists = [[]] Output: []
Constraints:
k == lists.length0 <= k <= 1040 <= lists[i].length <= 500-104 <= lists[i][j] <= 104lists[i]is sorted in ascending order.- The sum of
lists[i].lengthwill not exceed104.
For most of these solutions, we’ll be using the recursion-based LinkedList merger that we created for LeetCode challenge 21, “Merge two sorted lists”.
Approach) Merging all LinkedList objects into the first
This solution is probably the easiest to understand, but also the least efficient. Armed with our merge function, it’s fairly trivial to simply loop through all of the provided LinkedList elements, and merge their contents into the first LinkedList.
The merging function takes care of sorting, so we’re left with a fully merged, ordered LinkedList.
var mergeKLists = function (lists) {
// Return early if no ListNodes were supplied
if (!lists.length) return null;
// Loop through the supplied ListNodes
for (let i = 1; i < lists.length; i++) {
// Merge each ListNode with the first
lists[0] = merge(lists[0], lists[i]);
}
// Return the merged ListNode
return lists[0];
};
var merge = function (l1, l2) {
// If either list is empty, return the other list's node
if (l1 == null) return l2;
if (l2 == null) return l1;
// If l1 is lower
if (l1.val < l2.val) {
l1.next = merge(l1.next, l2);
return l1;
}
// If l2 is lower
else {
l2.next = merge(l1, l2.next);
return l2;
}
};The problem with this solution is efficiency. Because our merge operation is constantly being carried out on the ever-growing first LinkedList, it’s getting bigger and bigger each time.
It would be much more efficient to merge smaller LinkedList elements together, and then to merge their outputs together and so on, so that’s exactly what we’ll look at next.
Approach) Recursion
In this solution, we pass a recursive function to our array of LinkedList objects. That function then calculates the middle point, and calls itself again on both the left and middle, and the right + 1 and middle, or if there are insufficient LinkedLists remaining, it simply returns what it was given.
What this means is that we end up calling the function on every pair of LinkedLists, merging them together as we go. Therefore by the time the recursive function has worked its way back all the way to the top, we’re left with a single ordered LinkedList.
To use an example, let’s say we have 3 LinkedLists. We pass the function those lists, and it creates 2 merge-pairs; 1 + 2, and 3 + nothing. It then merges 1 with 2, and 3 with nothing, then it steps back and merges the combined 1+2 with 3+nothing, giving us a single, ordered LinkedList.
var mergeKLists = function (lists) {
if (lists == null || lists.length == 0) return null;
return sortLinkedLists(lists, 0, lists.length - 1);
};
var sortLinkedLists = function (lists, lo, hi) {
// If we no longer have multiple lists to merge, return the single LinkedList
if (lo >= hi) return lists[lo];
// Calculate the (rounded-down) middle point of the remaining lists
let mid = Math.floor(lo + (hi - lo) / 2);
// Merge and sort the left and middle lists
let l1 = sortLinkedLists(lists, lo, mid);
// Merge and sort the right and middle + 1 lists
let l2 = sortLinkedLists(lists, mid + 1, hi);
// Merge the two returned lists
return merge(l1, l2);
};
var merge = function (l1, l2) {
// If either list is empty, return the other list's node
if (l1 == null) return l2;
if (l2 == null) return l1;
// If l1 is lower
if (l1.val < l2.val) {
l1.next = merge(l1.next, l2);
return l1;
}
// If l2 is lower
else {
l2.next = merge(l1, l2.next);
return l2;
}
};Approach) Convert to an array
I’ll admit that this method is somewhat of a cheat, but it does work, and it works quickly too. What we do here is we traverse every provided LinkedList, adding their values to an overall array. We then order that array and convert it to a new LinkedList.
Note that the way we convert the array to a LinkedList is to do it in reverse order. This is because it allows us to create the last ListNode, which points to nothing, and then to create the second-to-last ListNode, which points to the last, and then the third-to-last ListNode, which points to the second-to-last, and then… well you get the idea.
Code:
var mergeKLists = function (lists) {
// Initialise an array to store the values in
let mainArray = [];
function addLinkedListToMainArray(subArray) {
// Push value of the LinkedList's current node to the main array
mainArray.push(subArray.val);
// Add the next node in the LinkedList
if (subArray.next != null) {
addLinkedListToMainArray(subArray.next);
}
}
// Loop through the supplied LinkedLists
for (let i = 0; i < lists.length; i++) {
// Check if the LinkedList is empty
if (lists[i] != null) {
// Add the LinkedList's contents to the main array
addLinkedListToMainArray(lists[i]);
}
}
// Sort the main array
mainArray = mainArray.sort((a, b) => a - b);
// Convert the array to a LinkedList
let newList = null;
for (i = mainArray.length - 1; i >= 0; i--) {
newList = new ListNode(mainArray[i], newList);
}
return newList;
};Conclusion
That’s all folks! In this post, we solved LeetCode problem #23. Merge k Sorted Lists
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment