开始之前

刚才做了反转链表，太简单，没挑战，来道 hard 给自己找点不痛快。

描述

合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。

数据范围

节点总数 0 <= n <= 5000

每个节点的 val 满足 |val| <= 1000

要求

时间复杂度 O(nlogn)

思路

暴力

把所有链表内的值压入数组，对数组排序(.sort(a,b)=>a-b）

然后把遍历数组构造一个新链表…

粗鲁… 太粗鲁了

分治+递归

在实现递归加分治前，我们要实现一个小算法

引申，合并两个已经排序的列表

描述

输入两个递增的链表，单个链表的长度为 n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围

0 <= n <= 1000，-1000 <= 节点值 <= 1000

要求

空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

思路

检查两个链表当前节点值，会有两种情况：

1. 如果链表 1 的当前节点值小于等于链表 2 的当前节点值

   • 将链表 2 的当前节点插入到链表 1 的当前节点后
   • 将链表 1 的当前节点指针后移到下一个节点去

2. 如果链表 1 的当前节点值大于链表 2 的当前节点值

   • 将链表 1 的当前节点插入到链表 2 的当前节点之后
   • 将链表 2 的当前节点指针后移到下一节点去

代码

function Merge(pHead1, pHead2) {
  // write code here

  // 设定递归结束条件为有一个为空则返回另一个
  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(pHead2.next, pHead1);
    return pHead2;
  }
}

代码解读

传入两个链表 1 和 2

这里我们使用了递归

入参检查后

如果链表 1 的当前节点值小于或等于链表 2 的当前节点值

那么，链表 1 当前节点保留，再递归去比较链表 1 的下一个节点和链表 2 的当前节点

如果链表 1 的当前节点值大于链表 2 的当前节点值

那么就保留链表 2 的当前节点，再递归比较链表 2 的下一个节点和链表 1 的当前节点

递归+分治

从引申问题回来，我们实现了两个链表的按序合并

那么接下来就是对链表进行遍历，先合并链表 2 到链表 1 中，再合并链表 3 到链表 1 中，再……直到遍历完链表组成的数组。

代码

暴力

暴力的代码比较直观粗俗

function mergeKLists(lists) {
  // write code here
  拿到所有的值后统一排序;
  let list = [];
  for (item of lists) {
    while (item) {
      list.push(item.val);
      item = item.next;
    }
  }

  list.sort((a, b) => a - b);
  let result = null;
  let head = null;
  for (item of list) {
    let node = new ListNode(item);
    if (head == null) {
      head = node;
      result = node;
    } else {
      head.next = node;
      head = head.next;
    }
  }
  return result;
}

递归+分治

function mergeKLists(lists) {
  for (let i = 0; i < lists.length; i++) {
    lists[0] = Merge(lists[0], lists[i + 1]);
    console.log(lists[i]);
  }
  return lists[0];
}

function Merge(pHead1, pHead2) {
  // write code here
  // 检查入参，有一个为空返回另一个
  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(pHead2.next, pHead1);
    return pHead2;
  }
}

相比较而言，递归加分治的方法可能不如暴力那么直观，但是要更巧妙一点。

递归这个它没法很直观的去了解，拿起笔和纸跟着走一遍是最直观的了。毕竟：你想理解递归那么首先你得理解递归。