合并K个排序链表

合并K个排序链表

0.说在前面1.合并K个排序链表2.作者的话

0.说在前面

每周两篇leetcode刷题,今天本周第二篇,一起来看合并K个排序链表,下面一起来实战吧!

1.合并K个排序链表

问题

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

示例:

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

算法一

思想

遍历k个链表,将每个链表中的节点值添加到list当中,然后排序,创建新链表!

实现

def mergeKLists(self, lists):
        all_list=[]
        for each in lists:
            while each:
                all_list.append(each.val)
                each=each.next
        all_list.sort()
        head=ListNode(0)
        p=head
        for i in all_list:
            p.next=ListNode(i)
            p=p.next
        p.next=None
        p=head.next
        del head
        return p

分析

假设其中最长链表长度为n,则时间复杂度为O(nk),空间复杂度为O(n)。

算法二

思想

两两链表合并,合并的时候采用递归进行合并,直到最后合并成一个链表,返回即可!

实现

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        interval = 1
        lists_len = len(lists)
        while interval<lists_len:
            for i in range(0,lists_len-interval,interval * 2):
                lists[i] = self.merge(lists[i], lists[i + interval]);
            interval *= 2
        return lists[0] if len(lists) > 0 else None
    def merge(self,l1, l2):
        if l1 is None:
            return l2
        if l2 is None:
            return l1
        if l1.val < l2.val:
            l1.next = self.merge(l1.next, l2)
            return l1
        else:
            l2.next = self.merge(l1, l2.next)
            return l2

分析

假设其中最长链表长度为n,两两合并时间复杂度O(n),每个链表遍历一次O(k)则,时间复杂度为O(nk),空间复杂度为O(1)。

本文分享自微信公众号 - 光城(guangcity)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-12-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员开发者社区

Logstash 配置 Grok 语法

Grok 是一种采用组合多个预定义的正则表达式。用来匹配分割文本,并且映射到关键字的工具。主要用来对日志数据进行预处理。Logstash 的 filter 模块...

36340
来自专栏小强的进阶之路

MySQL如何选择合适的索引

小强前几篇文章介绍了mysql的索引原理以及sql优化的一些小技巧。mysql底层的算法选择哪种索引,有时候会和我们想象的不一样,大家可以继续往下看。

9640
来自专栏汇智网教程

Ripple区块链对接PHP开发包【瑞波币/XRP】

XrpTool可以帮助PHP应用快速接入瑞波/Ripple区块链, 即支持部署自有Ripple节点的应用场景,也支持利用公开的Ripple节点广播离线裸交易的轻...

17550
来自专栏中科院渣渣博肆僧一枚

tf.RunMetadata

将_cached_byte_size_dirty位设置为true,并将其传播给侦听器(如果这是状态更改)。

12930
来自专栏中科院渣渣博肆僧一枚

tf.ReaderBase

用于不同读取器类型的基类,该基类将生成每个步骤的记录。从概念上讲,读取器将字符串“工作单元”转换为记录(键、值对)。通常,“工作单元”是文件名,记录是从这些文件...

7420
来自专栏网优小兵玩Python

【编程扫盲--数据结构】

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存...

7430
来自专栏dotnet & java

nacos 的服务注册与发现

这个要求服务统一注册到注册中心,然后调用的时候就不需要通过ip来调用,直接通过服务名即可。

25430
来自专栏Java那些事

JAVA面试解析(有赞二面)

说在前面的话: 本文适合人群:急等着换工作的人 我承认刷面试题很有用的,纵观几年来的JAVA面试题,你会发现每家都差不多。比如,你仔细观察,你会发现,HashM...

9630
来自专栏野路子程序员

PHP读取大文件源码示例-Swoole多进程读取大文件

在日常读取文件时,若文件 不是很大,通常使用file_get_contents,将内容一次性载入的变量中,也可以远程加载网页或者远端文件。

13430
来自专栏中科院渣渣博肆僧一枚

tf.RunOptions

将_cached_byte_size_dirty位设置为true,并将其传播给侦听器(如果这是状态更改)。

14220

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励