美文网首页
算法分析与设计(三)——合成K个排序链表

算法分析与设计(三)——合成K个排序链表

作者: itczt | 来源:发表于2019-05-27 21:52 被阅读0次

    一、问题描述

    合并 ķ 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

    示例:

    输入:
    [
    1-> 4-> 5,
    1-> 3-> 4,
    2-> 6
    ]
    输出: 1-> 1-> 2-> 3-> 4-> 4-> 5-> 6

    2.算法设计:

    方法1:暴力

    想法 & 算法

    • 遍历所有链表,将所有节点的值放到一个数组中。
    • 将这个数组排序,然后遍历所有元素得到正确顺序的值。
    • 用遍历得到的值,创建一个新的有序链表。

    关于排序,你可以参考 这里 获得更多关于排序算法的内容。

    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            """
            self.nodes = []
            head = point = ListNode(0)
            for l in lists:
                while l:
                    self.nodes.append(l.val)
                    l = l.next
            for x in sorted(self.nodes):
                point.next = ListNode(x)
                point = point.next
            return head.next
    

    复杂度分析

    • 时间复杂度:O(NlogN) ,其中 N 是节点的总数目。
      • 遍历所有的值需花费 O(N) 的时间。
      • 一个稳定的排序算法花费O(NlogN) 的时间。
      • 遍历同时创建新的有序链表花费O(N) 的时间。
    • 空间复杂度:O(N) 。
      • 排序花费 O(N) 空间(这取决于你选择的算法)。
      • 创建一个新的链表花费O(N) 的空间。

    相关文章

      网友评论

          本文标题:算法分析与设计(三)——合成K个排序链表

          本文链接:https://www.haomeiwen.com/subject/wfnktctx.html