LeetCode 热题 HOT 100 第十三天 23. 合并K个升序链表困难题用python3求解

53 阅读 0 评论 35 点赞

我是靠谱客的博主动听蛋挞，最近开发中收集的这篇文章主要介绍LeetCode 热题 HOT 100 第十三天 23. 合并K个升序链表困难题用python3求解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目地址

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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

在这里插入图片描述
思路
归并排序：先两两合并mergeTwoLists，然后对已经经过一次两两合并的链表们再进行一次两两合并，一直合并到生成最终的升序链表为止

mergeKLists步骤如下：
1.特判（即递归终止条件）：如果待合并的链表个数为0返回空，个数为1返回lists[0]无需合并
2.当待合并的链表个数大于等于2时，调用mergeTwoLists进行两两合并
3.这里mergeTwoLists的两个参数采用递归mergeKLists的方式，也就是对已经合并好的lists前一半的链表和后一半的链表进行合并，如果没合并好，先分别合并了再最终合并

复杂度分析

n为初始链表个数，m为初始链表们的最大长度

时间复杂度：O(nmlogn)
第一轮要合并n/2组链表，每一组时间O(2m)
第二轮要合并n/4组链表，每一组时间O(4m)
……
最后一轮要合并1组链表，每一组时间O(nm
每一轮的时间复杂度为O(nm)，总共有logn轮(n/2^x = 1 => x = logn)，最终时间复杂度为O(nmlogn)

空间复杂度：O(logn)O(logn)，递归栈大小

代码实现：

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        n = len(lists)
        if n == 0: return None
        if n == 1: return lists[0]
        
        mid = n // 2
        return self.mergeTwoLists(self.mergeKLists(lists[:mid]), self.mergeKLists(lists[mid:]))
    
    # 迭代写法 
    def mergeTwoLists(self, node1, node2):
        dummy = cur = ListNode()
        while node1 and node2:
            if node1.val <= node2.val:
                cur.next = node1
                node1 = node1.next
            else:
                cur.next = node2
                node2 = node2.next
            cur = cur.next
            print('cur:',cur)

        # 如果node1不为空(node1有剩余元素)，则剩下的全部连接到cur链表末尾；反之node2
        cur.next = node1 if node1 else node2
        return dummy.next

以示例一为例，代码中print的中间过程：
cur: ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}
cur: ListNode{val: 2, next: ListNode{val: 6, next: None}}
cur: ListNode{val: 3, next: ListNode{val: 4, next: None}}
cur: ListNode{val: 4, next: None}
cur: ListNode{val: 1, next: ListNode{val: 4, next: ListNode{val: 5, next: None}}}
cur: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 6, next: None}}}}}
cur: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 6, next: None}}}}
cur: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 6, next: None}}}
cur: ListNode{val: 4, next: ListNode{val: 5, next: None}}
cur: ListNode{val: 4, next: ListNode{val: 6, next: None}}
cur: ListNode{val: 5, next: None}