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

/*
 * 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,
};