1. 题目描述

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

  1. 输入：lists = [[1,4,5],[1,3,4],[2,6]]
  2. 输出：[1,1,2,3,4,4,5,6]
  3. 解释：链表数组如下：
  4. [
  5.   1->4->5,
  6.   1->3->4,
  7.   2->6
  8. ]
  9. 将它们合并到一个有序链表中得到。
  10. 1->1->2->3->4->4->5->6

示例 2：

  1. 输入：lists = []
  2. 输出：[]

示例 3：

  1. 输入：lists = [[]]
  2. 输出：[]

提示：

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

    2. 解题思路

    对于这道题目，我们可以每次合并两个链表，合并完成之后，更新数组，继续两两合并，使用递归完成合并即可。

复杂度分析：

  • 时间复杂度：O(NlogK)，K 条链表的总结点数是 N，平均每条链表有 N/K 个节点，因此合并两条链表的时间复杂度是 O(N/K)。从 K 条链表开始两两合并成一条链表，因此每条链表都会被合并 logK、 次，因此 K条链表会被合并 K logK 次，因此总共的时间复杂度是 K logK * N/K 即 O(NlogK)。
  • 空间复杂度：O(1)，没有用到与 K 和 N 规模相关的辅助空间，故渐进空间复杂度为 O(1)。

    3. 代码实现

    ```javascript /**
    • Definition for singly-linked list.
    • function ListNode(val, next) {
    • this.val = (val===undefined ? 0 : val)
    • this.next = (next===undefined ? null : next)
    • } / /*
    • @param {ListNode[]} lists
    • @return {ListNode} */ var mergeKLists = function(lists) { let len = lists.length if(!len){
      1. return null
      } if(len === 1){
      1. return lists[0]
      } // 将数组的前两项先进行合并 let res = mergeTwoKLists(lists[0], lists[1]) // 更新数组 lists.splice(0, 2, res) // 进行递归操作 return mergeKLists(lists) };

// 合并两个链表 function mergeTwoKLists(l1, l2){ let head = new ListNode(), pre = head while (l1 && l2) { if (l1.val > l2.val) { pre.next = l2 l2 = l2.next } else { pre.next = l1 l1 = l1.next } pre = pre.next } pre.next = l1 ? l1 : l2 return head.next } ```

4. 提交结果

image.png