我是靠谱客的博主 含糊大船,最近开发中收集的这篇文章主要介绍Python实现合并K个升序链表,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

题目描述

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

Leetcode原题地址:https://leetcode-cn.com/problems/merge-k-sorted-lists/

测试用例

  • 示例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 = [[]]
输出:[]

代码实现

  • 顺序合并

前面我们实现过2个升序链表的合并,K个链表的合并其实就是2个链表合并的升级版。定义一个最终的链表,先合并第一个和第二个,然后再合并第三…

from typing import List

class ListNode:
    def __init__(self,val=0,next=None):
        if isinstance(val,int):
            self.val = val
            self.next = next
        elif isinstance(val,list):
            self.val = val[0]
            self.next = None
            head = self
            for i in val[1:]:
                node = ListNode(i,None)
                head.next = node
                head = head.next

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:

        def mergeTwoLists(a: ListNode, b: ListNode):
            merge = ListNode(-1)
            head = merge
            while a and b:
                if a.val > b.val:
                    head.next = b
                    b = b.next
                else:
                    head.next = a
                    a = a.next
                head = head.next
            head.next = a if a else b
            return merge.next

        if len(lists) == 0:
            return None
        res = None
        for i in range(0,len(lists)):
            res = mergeTwoLists(res,lists[i])
        return res



lists = [[1,4,5],[1,3,4],[2,6]]
l_nodes = []
for l in lists:
    listnode = ListNode(l)
    l_nodes.append(listnode)


solution = Solution()
merge = solution.mergeKLists(l_nodes)
while merge:
    print(merge.val)
    merge = merge.next
  • 分治法合并

在使用顺序合并的时候存在很多重复的操作,从而导致合并的时间会很长,其实我们可以先将整个链表分成两大块,然后再继续切分,最后分到左边和右边的链表长度为1时,再往上进行合并
在这里插入图片描述

class Solution:
    def mergeTwoList(self,a:ListNode,b:ListNode):
        merge = ListNode(-1)
        head = merge
        while a and b:
            if a.val > b.val:
                head.next = b
                b = b.next
            else:
                head.next = a
                a = a.next
            head = head.next

        head.next = a if a else b
        return merge.next

    def merge(self,left,right):
        if left == right:
            return self._lists[left]
        if left > right:
            return None
        middle = (left+right) // 2
        return self.mergeTwoList(self.merge(left,middle),self.merge(middle+1,right))


    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        self._lists = lists
        return self.merge(0,len(lists)-1)

参考:合并K个排序链表

最后

以上就是含糊大船为你收集整理的Python实现合并K个升序链表的全部内容,希望文章能够帮你解决Python实现合并K个升序链表所遇到的程序开发问题。

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

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(41)

评论列表共有 0 条评论

立即
投稿
返回
顶部