题解 | #合并k个已排序的链表#
合并k个已排序的链表
https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
/*
* function ListNode(x){
* this.val = x;
* this.next = null;
* }
*/
/**
*
* @param lists ListNode类一维数组
* @return ListNode类
*/
function mergeKLists(lists) {
// write code here
if (lists.length === 1) return lists[0];
return mergeLRList(lists, 0, lists.length - 1);
}
//分治函数
function mergeLRList(lists, left, right) {
if (left >= right) return left === right ? lists[left] : null;
let middle = Math.floor((left + right)/2)
return Merge(
mergeLRList(lists,left,middle),
mergeLRList(lists,middle+1,right)
)
}
//合并两个链表函数
function Merge(pHead1, pHead2) {
if (!pHead1) return pHead2;
if (!pHead2) return pHead1;
if (pHead1.val <= pHead2.val) {
pHead1.next = Merge(pHead1.next, pHead2);
return pHead1;
} else {
pHead2.next = Merge(pHead1, pHead2.next);
return pHead2;
}
}
module.exports = {
mergeKLists: mergeKLists,
};