（每日一练python）合并K个升序链表合并K个升序链表

合并K个升序链表

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

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

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

以下程序实现了这一功能，请你填补空白处内容：

from typing import List


class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class LinkList:
    def __init__(self):
        self.head = None

    def initList(self, data):
        self.head = ListNode(data[0])
        r = self.head
        p = self.head
        for i in data[1:]:
            node = ListNode(i)
            p.next = node
            p = p.next
        return r

    def convert_list(self, head):
        ret = []
        if head == None:
            return
        node = head
        while node != None:
            ret.append(node.val)
            node = node.next
        return ret


class Solution(object):
    def mergeKLists(self, lists):
        if lists is None:
            return None
        elif len(lists) == 0:
            return None
        return self.mergeK(lists, 0, len(lists) - 1)

    def mergeK(self, lists, low, high):
        if low == high:
            return lists[int(low)]
        elif low + 1 == high:
            return self.mergeTwolists(lists[int(low)], lists[int(high)])
        mid = (low + high) / 2
        return self.mergeTwolists(self.mergeK(lists, low, mid),
                                  self.mergeK(lists, mid + 1, high))

    def mergeTwolists(self, l1, l2):
        l = LinkList()
        if type(l1) == list:
            l1 = l.initList(l1)
        if type(l2) == list:
            l2 = l.initList(l2)
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        head = curr = ListNode(-1)
        while l1 is not None and l2 is not None:
			if l1.val <= l2.val:
	            curr.next = l1
	            l1 = l1.next
            else:
            	curr.next = l2
            	l2 = l2.next
            curr = curr.next
        if l1 is not None:
            curr.next = l1
        if l2 is not None:
            curr.next = l2
        return head.next


# %%
l = LinkList()
list1 = [[1, 4, 5], [1, 3, 4], [2, 6]]
s = Solution()
print(l.convert_list(s.mergeKLists(list1)))

最后

以上就是尊敬哑铃为你收集整理的（每日一练python）合并K个升序链表合并K个升序链表的全部内容，希望文章能够帮你解决（每日一练python）合并K个升序链表合并K个升序链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。