题解 | #合并k个已排序的链表#

使用递归合并两个有序链表，使用分治法对数组进行合并排序

/**
*@description 使用递归排序对两个有序链表合并排序
*@param 需要合并的两个链表的头指针
*@return 合并好的链表
*/
function Merge(pHead1, pHead2) {
    if(!pHead1 || !pHead2) return pHead1? pHead1: pHead2;
    if(pHead1.val <= pHead2.val) {
        pHead1.next = Merge(pHead1.next, pHead2);
        return pHead1;
    }else {
        pHead2.next = Merge(pHead1, pHead2.next);
    }
}
/**
*@description 使用分治法进行给定数组的合并
*@param lists 需要处理的链表数组 left 起始索引 right 结束索引
*@return 处理好的单链表
**/
function MergeList(lists, left, right) {
    //判断起始位置是否小于结束位置
    if(left >= right) return left === right? lists[left]: null;
    let middle = Math.floor((left + right)/ 2);
    return Merge(MergeList(lists, left, middle), MergeList(lists, middle + 1, right));
}
/**
*@descripotion 根据给定的数组进行排序
*@param 多个链表子项形成的数组
*@return 升序排序的单链表
**/
function mergeKLists( lists ) {
    // write code here
    if(lists.length <= 1) return lists[0] || null;
    return MergeList(lists, 0, lists.length -1);
}