Algorithm
Problem Name: 23. Merge k Sorted Lists
Problem Link: https://leetcode.com/problems/merge-k-sorted-lists/
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.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
struct ListNode *merge(struct ListNode *a, struct ListNode *b) {
struct ListNode head, *prev, *c;
prev = &head;
while (a && b) {
if (a->val < b->val) {
c = a;
a = a->next;
} else {
c = b;
b = b->next;
}
prev->next = c;
prev = c;
}
prev->next = a ? a : b;
return head.next;
}
struct ListNode *divide_and_merge(struct ListNode **lists, int start, int end) {
int mid;
struct ListNode *a, *b;
if (start == end) return lists[start];
mid = start + (end - start) / 2;
a = divide_and_merge(lists, start, mid);
b = divide_and_merge(lists, mid + 1, end);
return merge(a, b);
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
struct ListNode *head = NULL;
if (listsSize == 0) return NULL;
#if 0 // 245ms
int i;
struct ListNode *a, *b;
a = lists[0];
for (i = 1; i < listsSize; i ++) {
b = lists[i];
a = merge(a, b);
}
head = a;
#else // 9ms O(NKlogK) N is average length of a list, K is number of lists
head = divide_and_merge(lists, 0, listsSize - 1);
#endif
return head;
}
Input
lists = [[1,4,5],[1,3,4],[2,6]]
Output
[1,1,2,3,4,4,5,6]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.size() == 0) return NULL;
for (int i = 0, j = 1; j < lists.size(); i++, j++)
lists[j] = mergeTwoLists(lists[i], lists[j]);
return *(lists.end() - 1);
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1 || !l2) return l1 ? l1 : l2;
ListNode head(0);
ListNode* cur = &head;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
}
else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2;
return head.next;
}
};
Input
lists = []
Output
[]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode listNode : lists) {
if (listNode != null) {
pq.add(listNode);
}
}
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (!pq.isEmpty()) {
ListNode removed = pq.remove();
curr.next = new ListNode(removed.val);
curr = curr.next;
if (removed.next != null) {
pq.add(removed.next);
}
}
return dummy.next;
}
}
Input
lists = [[]]
Output
[]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const mergeKLists = function(lists) {
return merge(lists, 0, lists.length - 1)
}
function merge(lists, l, r) {
if (l > r) return null
if (l === r) return lists[l]
let m = Math.floor((r + l) / 2)
let left = merge(lists, l, m)
let right = merge(lists, m + 1, r)
let head = new ListNode(0)
let dummy = head
while (left && right) {
if (left.val <= right.val) {
head.next = left
left = left.next
} else {
head.next = right
right = right.next
}
head = head.next
}
head.next = left ? left : right
return dummy.next
}
Input
lists = []
Output
[]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def mergeKLists(self, lists):
q = []
for i in range(len(lists)):
while lists[i]:
q += lists[i],
lists[i] = lists[i].next
root = cur = ListNode(0)
for h in sorted(q, key = lambda x: x.val):
cur.next = cur = h
return root.next
Input
lists = [[]]
Output
[]
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _023_MergeKSortedLists
{
public ListNode MergeKLists(ListNode[] lists)
{
if (lists == null || lists.Length == 0) return null;
return MergeKHelper(lists, 0, lists.Length - 1);
}
public ListNode MergeKHelper(ListNode[] lists, int i, int j)
{
if (i == j) return lists[i];
int mid = i + (j - i) / 2;
var left = MergeKHelper(lists, i, mid);
var right = MergeKHelper(lists, mid + 1, j);
return MergeTwoLists(left, right);
}
private ListNode MergeTwoLists(ListNode l1, ListNode l2)
{
var head = new ListNode(-1);
var current = head;
while (l1 != null && l2 != null)
{
if (l1.val < = l2.val)
{
current.next = l1;
l1 = l1.next;
}
else
{
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 == null ? l2 : l1;
return head.next;
}
}
}
Input
lists = []
Output
[]