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

BM5 合并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;
  }
}

// 方法二
// 将 lists 中所有链表的每个值都放入 arr，
// 对 arr 排序 sort()
// 将 arr 转为新的链表

module.exports = {
  mergeKLists: mergeKLists,
};

如有问题望指正