python实现合并两个有序列表的示例代码
作者:修炼之路 发布时间:2021-06-02 20:07:29
标签:python,合并,有序列表
题目描述
将两个升序链表
合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
LeetCode原题地址:https://leetcode-cn.com/problems/merge-two-sorted-lists/
测试用例
示例1
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例2
输入:l1 = [], l2 = []
输出:[]
示例3
输入:l1 = [], l2 = [0]
输出:[0]
代码详解
因为LeetCode服务器上已经封装了链表类,在本地测试时我需要自己来实现链表类,代码如下
class ListNode:
def __init__(self, val, 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 range(1,len(val)):
node = ListNode(val[i],None)
head.next = node
head = head.next
递归法
递归法的思路比较简单,我们需要先判断链表l1
和链表l2
是否为空,如果为空直接返回另一个链表即可就不需要进行比较了。如果不为空,我们就需要比较链表节点的值谁的更大,如果l1大于l2
我们就更改链表l2的下一个节点,然后再比较l2的下一个节点和l1,反之可得另一种情况的处理方法。
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
#如果链表l1为None直接返回链表l2即可
if l1 is None:
return l2
#如果链表l2为None直接返回链表l1即可
elif l2 is None:
return l1
#如果链表l1大于链表l2
elif l1.val > l2.val:
#更改链表l2下一个节点的指向
l2.next = self.mergeTwoLists(l1,l2.next)
return l2
else:
#更改链表l1下一个节点的指向
l1.next = self.mergeTwoLists(l1.next,l2)
return l1
l1 = ListNode([1,2,4])
l2 = ListNode([1,3,4])
s = Solution()
l = s.mergeTwoLists(l1,l2)
while l:
print(l.val)
l = l.next
遍历法
这个算法更简单了,我们只需要遍历链表l1和l2然后再比较大小即可,对于最后没遍历完的部分,直接追加到合并链表的后面即可。
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
#用来合并链表
prehead = ListNode(-1)
#创建一个哨兵节点
pre = prehead
while l1 and l2:
if l1.val > l2.val:
pre.next = l2
l2 = l2.next
else:
pre.next = l1
l1 = l1.next
#更改哨兵节点的下一个指向
pre = pre.next
pre.next = l1 if l1 else l2
return prehead.next
l1 = ListNode([1,2,4])
l2 = ListNode([1,3,4])
s = Solution()
l = s.mergeTwoLists(l1,l2)
while l:
print(l.val)
l = l.next
参考:合并两个有序链表
来源:https://blog.csdn.net/sinat_29957455/article/details/113420273
0
投稿
猜你喜欢
- Application对象 Application对象是个应用程序级的对象,用来在所有用户间共享信息,并可以在Web应用程序运行期间持久地保
- rfind()方法返回所在子str 被找到的最后一个索引,或者-1,如果没有这样的索引不存在,可选择限制搜索字符串string[
- 这篇文章主要介绍了python自动化unittest yaml使用过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参
- 简单的学习下利用socket来建立客户端和服务端之间的连接并且发送数据1. 客户端socketClient.py代码import socke
- 上一篇已经介绍了celery的基本知识,本篇以一个小项目为例,详细说明django框架如何集成celery进行开发。本系列文章的开发环境:w
- python实现猫捉老鼠小游戏首界面开始游戏界面然后键盘操作小老鼠上下左右移动,猫自己去追,当猫追上老鼠则游戏结束这里用时3.2秒,最后将游
- 内容摘要:最近在做项目的时候,客户要求表格里的数据可以拖选,于是用JS写了个下面的方法。支持IE、FIREFOX等浏览器。实现对整行、整列数
- 介绍Zmail 使得在python3中发送和接受邮件变得更简单。你不需要手动添加服务器地址、端口以及适合的协议,zmail会帮你完成。此外,
- 操作:输入带分页的地址,去掉最后面的数字,设置一下起始页数和终点页数功能:下载对应页码的所有页面并储存为HTML文件,以当前时间命名代码:#
- 最近在实习,boss给布置了一个python的小任务,学习过程中发现copy()和deepcopy()这对好 * 实在是有点过分,搞的博主就有
- 在使用google或者baidu搜图的时候会发现有一个图片颜色选项,感觉非常有意思,有人可能会想这肯定是人为的去划分的,呵呵,有这种可能,但
- 原始需求:例如有一个列表:l = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]希望把它转换成下面这种形式:[1, 2,
- 由于该math模块与 Python 版本一起打包,因此您不必单独安装它,直接导入:import mathmath模块常数Pythonmath
- Python读取及保存mat文件在说明python读取mat文件之前需要强调2点:读取的时候需要注意读出来的shape是什么样的,是否符合自
- 在1943年,沃伦麦卡洛可与沃尔特皮茨提出了第一个脑神经元的抽象模型,简称麦卡洛可-皮茨神经元(McCullock-Pitts neuron
- 简介 本次项目登录注册验证是对之前学习知识点的加深学习,这次项目的练习的知识点有函数、判断语句、循环语句、文件操作等。项目流程 运行代码之后
- 支付宝或者微信支付导出的收款二维码,除了二维码部分,还有很大一块背景图案,例如下面就是微信支付的收款二维码:有时候我们仅仅只想要图片中间的方
- 用HZHOST实用工具集的服务器安全设置里安装了MSSQL安全配置,现在SQL2000还原不了数据库了,从还原选定设备浏览文件夹时出现&qu
- 一、基本用法Queue类实现了一个基本的先进先出容器。使用put()将元素增加到这个序列的一端,使用get()从另一端删除。具体代码如下所示
- 当我们使用访问一个没有声明的变量时,JS会报错;而当我们给一个没有声明的变量赋值时,JS不会报错误,相反它会认为我们是要隐式申明一个全局变量