python合并k个有序链表_Leetcode合并K个升序链表（Python版本）,LeetCode,python
一、描述
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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
二、理解
首先，意识到数组中每个元素是一个链表，要注意和列表的区别；其次，每个链表都是升序的，因此两个链表合二为一可以在线性时间内完成。
思路
将前两个链表合二为一，将新链表与第三个链表合二为一，......，将新链表与第n个链表合二为一。
一些特殊情况为
空数组，直接返回，没有返回值，有返回值便通不过，不知是LeetCode的问题还是我理解的有问题；只有一个链表，直接返回链表头。
小技巧
提示中说明了链表元素的最小值是-10000，可提前生成一个值为-10001的链表头，否则你要在两个链表的首元素中选择一个作为链表头。
这也是为何第三部分代码最后一行是 return head.next 而不是 return head 的原因。
三、代码(初级版)
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
k = len(lists)
head = ListNode(val=-10001)
tail = head
if k == 0: return
if k == 1: return lists[0]
lp = lists[0]
rp = None
i = 1
# 将已完成合并的链表与当前链表数组中的第i个链表进行合并
while i < k:
rp = lists[i]
while lp and rp:
if lp.val <= rp.val:
tail.next = lp
tail = lp
lp = lp.next
else:
tail.next = rp
tail = rp
rp = rp.next
if rp: tail.next = rp
if lp: tail.next = lp
i += 1
# 如果数组没有遍历完，则重置头指针和尾指针
if i < k:
lp = head.next
head.next = None
tail = head
return head.next
上述代码虽然通过了测试，但下述结果并不是特别理想。
执行用时：3916 ms, 在所有 Python 提交中击败了15.47%的用户
内存消耗：19.1 MB, 在所有 Python 提交中击败了41.84%的用户
算法复杂度为
，n 为所有的链表节点数。
四、优化版
在优化版本中，注意是意识到了可以效仿归并排序的做法，下面是代码。
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, nxt=None):
self.val = val
self.next = nxt
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
k = len(lists)
if k == 0: return
if k == 1: return lists[0]
mid = k / 2
lp = self.mergeKLists(lists[0:mid])
rp = self.mergeKLists(lists[mid:])
head = ListNode(val=-10001)
tail = head
while lp and rp:
if lp.val <= rp.val:
tail.next = lp
tail = lp
lp = lp.next
else:
tail.next = rp
tail = rp
rp = rp.next
if lp: tail.next = lp
if rp: tail.next = rp
return head.next
这次的执行结果
执行用时：92 ms, 在所有 Python 提交中击败了73.96% 的用户
内存消耗：18.9 MB, 在所有 Python 提交中击败了43.94% 的用户
算法复杂度为
，n 为所有的链表节点数。
相关文章：
Qt界面风格设置
每个widget都可以设置风格setStyle(QStyle style)对QApplication设置QStyle即对所有QApplication::setStyle(QStyleFactory::create("Fusion"));其他widget如过没有被设置QStyle，默认使用QApplication的QStyle主要可重写接口绘制复杂控件virtual void …
树莓派练习程序（蜂鸣器）
蜂鸣器模块如下图： 树莓派的引脚如下图： 我们将Vcc引脚连接物理接口1（注意这里需要用3.3v），I/O引脚连接物理接口40，GND引脚连接物理接口39。 实物连接如下图： 编程使用WiringPi库，使…
Gold Code，Gold Sequence
Gold Code Gold Code是以Robert Gold的名字命名的。它是一组特殊的二进制随机(伪随机)序列，其中成员序列之间的相关性很小。由于这种特性(较小的相关性)，它被广泛地用作各种无线通信系统的扰码。 我们可以非常简单地利用 m序列 来生成Gold Code: 选择两…
【PHP高效搜索专题(1)】sphinxCoreseek的介绍与安装
我们已经知道mysql中带有"%keyword%"条件的sql是不走索引的,而不走索引的sql在大数据量大并发量的时候,不仅效率极慢还很有可能让数据库崩溃.那我们如何通过某些关键字来搜索我们想要的文章呢? 虽然mysql的MYISAM提供全文索引,但是只支持中文,并且性能却不敢让人恭维…
java 开源sns_JEESNS V1.0发布，JAVA 开源 SNS 社交系统
JEESNS V1.0 发布了，本次更新内容：增加后台管理员授权与取消功能增加私信模块解决在微博页面，左侧微博点赞过后，左侧展示列表小手会变黑，但是右侧热门出小手依然是白色修复后台添加栏目、文章成功后，提示页…
Balanced Binary Tree leetcode java
题目：Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. 题解：采用递归…
leaflet地图框架
leaflet 中文API LeafLet js 官网： http://leafletjs.com/index.html LeafLet js 官网demo： http://leafletjs.com/examples.html LeafLet js 官网API： http://leafletjs.com/reference-1.3.0.html L.Map API各种类中的核心部分，用…
NR:UE初始搜网流程
UE的初始搜网流程，PSS->SSS->PBCH->RMSI.我画了一个简单的流程图如下，里面标注了每个环节的重点。 UE的初始搜网流程: 分为SSB同步(包括MIB读取)和RMSI的读取。 1. SSB SSB包括： PSS,SSS,PBCH. UE 在GSCN频点上，搜索…
纯CSS3制作的圆角效果按钮菜单
<!DOCTYPE html> <head> <meta http-equiv"Content-Type" content"text/html; charsetutf-8" /> <title>纯CSS3制作的圆角效果按钮菜单丨曲阳雕塑</title> <style type"text/css"> nav{display: block; wid…
java 左右键_js 区分鼠标左右键点击
oncontextmenu 是右键事件但是滚轮事件并没有获取到, 使用vue可以用middle获取Title.box {width: 200px;height: 200px;background: deepskyblue;}let div document.getElementById(app)div.oncontextmenu function (e) {e.preventDefault();console.log(右键, e.button)};d…
面向对象设计领域的OCP原则
一、OCP简介（OCP--Open-Closed Principle ）：Software entities(classes,modules,functions,etc.) should be open for extension, but closed for modification。软件实体应当对扩展开放，对修改关闭，即软件实体应当在不…
Python教学课程分享9-面向对象编程
面向对象程序设计的思想主要是针对大型软件设计而提出的，它的一个关键性观念是将数据以及对数据的操作封装在一起，组成一个相互依存、不可分割的整体，即不同对象之间通过消息机制来通信或者同步。对于相同类型对象进行分类、抽象后࿰…
UE capability与 双连接相关的参数。
UE capability 分为 Network capability 和 Radio capability, 即网络能力和无线能力。 Netowrk Capability UE 在做Attach Request 时会主动上报自己的网络能力；Radio Capability 网络侧下发Enquiry Capability来请求UE无线能力，UE 回复capability inf…
Linux下Tomcat的安装配置
Linux下Tomcat的安装配置 一.下载安装对应的jdk,并配置Java环境。 官网下载地址： http://www.oracle.com/technetwork/java/javase/downloads/jdk-6u26-download-400750.html 下载将jdk加压后放到/usr/local目录下： [rootmaster ~]#chmod 755 jdk-6u5-li…
python登录代码思路_用python登录Dr.com思路以及代码分享
用python登录Dr.com思路以及代码分享发布于 2014-08-28 22:31:52 | 192 次阅读 | 评论: 0 | 来源: 网友投递Python编程语言Python 是一种面向对象、解释型计算机程序设计语言，由Guido van Rossum于1989年底发明，第一个公开发行版发行于1991年。Python语法…
postgresql开发中可能有用的知识
2019独角兽企业重金招聘Python工程师标准>>> postgresql手册 一、PostgreSQL中可以直接对时间进行加减运算： 查询系统当前时间： select now();或者select current_timestamp;SELECT now()::timestamp 1 year; --当前时间加1年SELECT now():…
css实现 textarea 高度自适应
此textarea非彼textarea ，有经验的老司机们应该知道html标签contenteditable这个属性。 利用此属性使当前的标签成为可以输入的状态，等同于输入框。 演示地址：https://xibushijie.github.io/static/textareaHeihgAuto.html <!DOCTYPE html…
LTE PUCCH Format1
PUCCH 格式 1/1a/1b 是向eNodeB传递1或2或4位数据。 这个过程相当复杂，我们用如下3个章节来描述： PUCCH Format 1,1a,1b 所在RB位置PUCCH F1信号的生成PUCCH 多UE 复用 PUCCH Format 1,1a,1b 所在RB位置 LTE中有很多课题(尤其是物理层)，如…
innodb force recovery
innodb force recovery的6种设置： 1.innodb force recovery1，即使发现了损坏页面也继续让服务器继续运行，这个选项对于备份或者转存当前数据尤为有用2.innodb force recovery2，阻止恢复主线程的运行，如果清除操作会导致…
随机森林 java_机器学习weka，java api调用随机森林及保存模型
工作需要，了解了一下weka的java api，主要是随机森林这一块，刚开始学习，记录下。了解不多，直接上demo，里面有一些注释说明：package weka;import java.io.File;import weka.classifiers.Classifie…
[转载]64位linux安装WPS
2019独角兽企业重金招聘Python工程师标准>>> 网上下载了最新的WPS＊.deb 安装后发现运行不了。（点Unity > WP搜出来的图标） 还以为安装有问题。于是重装了几次。还是不成功。 然后打开终端 wps 原来是程序出错了 提示找不到/opt…
mybatis报错There is no getter for property named '***' in 'class ***'
mybatis报错There is no getter for property named *** in class ***， 检查一看是xml中映射字段拼写错误，大小写。 有的时候用插件生成了原始的代码没问题，增加了一个字段在没有再自动生成的时候， 喜欢自己手动加一部分进去&…
LTE - PUCCH Format2
LTE中有很多课题(尤其是物理层)，如果不仔细阅读规范中给出的每个参数和方程，是无法解释清楚的。物理资源分配就是其中之一。 PUCCH格式2/2a/2b的物理资源分配由以下过程确定。看到这些公式千万不要惊慌，方程本身就是高中数学的一部分…
数据绑定（Binding）
Windows Presentation Foundation (WPF) 中的数据绑定为应用程序提供了一种简单、一致的数据表示和交互方法。元素能够以公共语言运行时 (CLR) 对象和 XML 形式绑定到来自各种数据源的数据。 什么是数据绑定？ 数据绑定是在应用程序 UI 与业务逻辑之间建立连接的过程…
java exception源码_Java异常之 Error 和 Exception
简单了解 Java 异常1、实际工作中，遇到的情况不可能是非常完美的。比如：你写的某个模块，用户输入不一定符合你的要求；你的程序要打开某个文件，这个文件可能不存在或者文件格式不对；你要读取数据库的数据&am…
面向对象解决了全局变量问题？
2019独角兽企业重金招聘Python工程师标准>>> 全局变量的应用场景 程序中的某些资源之多能有一个，比如计数器、配置信息、程序运行状态等，而且许多地方需要访问他，那么这个资源就应该，也只能设置成全局变量。在稍微大点…
物理层UL基本流程
物理层发端的基本流程在36.211/36.212(NR:38.211/38.212)中有详细的描述，现在归纳如下。下面列出的每个步骤对于某些信道而言可能会增加其它步骤，也可能有些步骤不需要。 CRC 相关 信道编码(channel coding) LTE: NR: 加扰-Scrambling 加扰过程是da…
java 建树源码_Java实现的二叉树常用操作【前序建树，前中后递归非递归遍历及层序遍历】...
import java.util.ArrayDeque;import java.util.Queue;import java.util.Stack;//二叉树的建树，前中后 递归非递归遍历 层序遍历//Node节点class Node {int element;Node left;Node right;public Node() {}public Node(int element) {this.element element;}}// Bi…
html5小趣味知识点系列（一）autofocus
<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>autofocus</title> </head> <body><input type"text" autofocus value"页面中只能有一个哦"><!-- 如…
cisco aaa 授权后门测试
最近遇到一个客户aaa没有正确的配置，导致自己被关在设备外面的case；由于是生产环境的多交换机堆叠单元，重启忽略配置也是不允许的，且必须远程操作解决，无疑提升了解决问题的难度。多次尝试后发现通过cisco acs上的一些…