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 <= 10^4`
• `0 <= lists[i].length <= 500`
• `-10^4 <= lists[i][j] <= 10^4`
• `lists[i]` is sorted in ascending order.
• The sum of `lists[i].length` won’t exceed `10^4`.

Idea:

Divide and Conquer

Solution:

``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
return merge(lists, 0, lists.length - 1);
};

function merge(lists, l , r) {
if (lists.length === 0) return null;
if (l === r) return lists[l];
let mid = Math.floor((l + r) / 2);
let l1 = merge(lists, l, mid);
let l2 = merge(lists, mid + 1, r);
return mergeTwoLists(l1, l2);
}

var mergeTwoLists = function(l1, l2) {
// If one of the list is empty, return the other one.
if (l1 === null) {
return l2;
}
if (l2 === null) {
return l1;
}

// The smaller one becomes the head.
if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
};``````