Appearance
23. 合并K个升序链表
题目描述
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
- 输入： lists =
[[1,4,5],[1,3,4],[2,6]] - 输出：
[1,1,2,3,4,4,5,6] - 解释： 链表数组如下：
[ 1->4->5, 1->3->4, 2->6 ]将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2：
- 输入： lists = []
- 输出： []
示例 3：
- 输入： lists =
[[]] - 输出： []
提示：
k == lists.length0 <= k <= 10^40 <=lists[i].length <= 500-10^4 <=lists[i]``[j]<= 10^4lists[i]按 升序 排列``lists[i]
.length的总和不超过10^4
难度： Hard
题解代码
javascript
/**
* Definition for singly-linked list.
* function
* (val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
if (!lists.length) return null
let res = lists[0]
for (let i = 1; i < lists.length; i++) {
res = mergeTwoLists(res, lists[i])
}
return res
};
var mergeTwoLists = function(l1, l2) {
const preHead = new ListNode(-1)
let p = preHead
while (l1 && l2) {
if (l1.val > l2.val) {
p.next = l2
l2 = l2.next
} else {
p.next = l1
l1 = l1.next
}
p = p.next
}
p.next = l1 || l2
return preHead.next
};