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 = [[]]
输出：[]
- 1、自己写的，主要利用的是数组的排序
.
var mergeKLists = function(lists) {
let result = [];
// 取出所有值
for(item of lists) {
while(item !== null) {
result.push(item.val);
item = item.next
}
}
// 排序
result = result.sort((i,j) => i - j);
// 重新创建链表
let head = new ListNode(-1);
let temp = head;
while(result.length){
const newNode = new ListNode(result.shift())
head.next = newNode;
head = head.next;
}
return temp.next;
};
看到一个上文方法的简写法，惊为天人 -> 但是理解起来比较复杂
var mergeKLists = function(lists) {
return lists.reduce((p, c) => {
while (c) {
p.push(c), // 推入的是一个链表
c = c.next // 每次都移除链表的第一项
}
return p
},[])
/**
假设输入的 lists 是 [[1,4,5],[1,3,4],[2,6]]，上文 reduce 得到的结果是
[[1,4,5], [4,5],[5], [1,3,4],[3,4],[4], [2,6],[6]]
*/
.sort((a, b) => a.val - b.val)
/**
这里利用排序只取链表的第一项的 val 比较，得到按照链表第一位排序后的链表
[[1,4,5], [1,3,4],[2,6],[3,4],[4,5],[4],[5],[6]]
*/
.reduceRight((p, n) => (n.next = p, p = n, p), null)
/**
reduceRight 表示从右向左遍历
p 作用类似指针，每次都往数组中的每个链表第一项移动；
n.next = p 将每个链表第一项使用 next 进行连接
最后 p = n，返回 p，得到结果
*/
};
- 2.方法：递归，两两合并链表
想法：
var mergeKLists = function(lists) {
// 合并两个链表的函数
const mergeTwoLists = function (l1, l2) {
if (l1 === null) {
return l2;
} else if (l2 === null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
// 兼容lists 为 []
if(!lists.length) return null;
let res = lists.shift();
while(lists.length) {
res = mergeTwoLists(res, lists.shift());
}
return res
}