2021-03-24 | 23. 合并K个升序链表

左手的ㄟ右手 2022-11-13 01:56 121阅读 0赞

### 1. 题目描述 ###

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

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

**示例 1：**

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

**示例 2：**

输入：lists = []
    输出：[]

**示例 3：**

输入：lists = [[]]
    输出：[]

**提示：**

*  `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. 代码实现 ###

/** * 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){ 
            return null
        }
        if(len === 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. 提交结果 ###

![在这里插入图片描述][20210324233640262.png]

[20210324233640262.png]: /images/20221022/33cbe69bf5114e54b69920677d64d644.png?