## Algorithm

Problem Name: 23. Merge k Sorted Lists

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

Example 1:

```Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
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.length`
• `0 <= k <= 104`
• `0 <= lists[i].length <= 500`
• `-104 <= lists[i][j] <= 104`
• `lists[i]` is sorted in ascending order.
• The sum of `lists[i].length` will not exceed `104`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
struct ListNode *merge(struct ListNode *a, struct ListNode *b) {
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;
}
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) {

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);
}
#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
}
``````
Copy The Code &

Input

cmd
lists = [[1,4,5],[1,3,4],[2,6]]

Output

cmd
[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;
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;
}
};
``````
Copy The Code &

Input

cmd
lists = []

Output

cmd
[]

### #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) {
}
}
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) {
}
}
return dummy.next;
}
}
``````
Copy The Code &

Input

cmd
lists = [[]]

Output

cmd
[]

### #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)
while (left && right) {
if (left.val <= right.val) {
left = left.next
} else {
right = right.next
}
}
head.next = left ? left : right
return dummy.next
}
``````
Copy The Code &

Input

cmd
lists = []

Output

cmd
[]

### #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
``````
Copy The Code &

Input

cmd
lists = [[]]

Output

cmd
[]

### #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)
{

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;
}
}
}
``````
Copy The Code &

Input

cmd
lists = []

Output

cmd
[]