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.length`
- `0 <= k <= 10^4`
- `0 <= lists[i].length <= 500`
- `-10^4 <= lists[i][j] <= 10^4`
- `lists[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
};