python实现合并两个有序列表的示例代码
作者:修炼之路 时间:2021-06-02 20:07:29
题目描述
将两个升序链表
合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
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
标签:python,合并,有序列表


猜你喜欢
Python 用户登录验证的小例子
2021-07-04 09:39:25
mysql 5.7.11 winx64安装配置方法图文教程
2024-01-18 11:57:59

wap开发 完整的WML文档结构详解
2008-05-21 13:39:00
SQL优化基础 使用索引(一个小例子)
2012-01-29 18:29:26
Windows系统下实现pycharm运行.sh文件(本地运行和打开服务器终端)
2021-03-04 23:53:45

vue2 利用echarts 单独绘制省份的步骤
2024-04-09 10:45:42

Python德劳内三角剖分详解
2021-02-18 23:08:49

nodejs处理tcp连接的核心流程
2024-05-03 15:55:40
python 如何读取列表中字典的value值
2021-01-27 15:48:31

Python实现base64编码的图片保存到本地功能示例
2024-01-01 22:58:03

解决在window下执行SQLSERVER定时备份的问题
2024-01-13 15:17:09

Mysql中explain的使用详解
2009-12-08 16:18:00
Python使用smtp和pop简单收发邮件完整实例
2022-01-07 05:48:40
详解Python中元组的三个不常用特性
2021-09-02 05:49:35
python中while循环语句用法简单实例
2021-12-03 22:34:44
超详细注释之OpenCV更改像素与修改图像通道
2021-07-01 17:42:45

纯python进行矩阵的相乘运算的方法示例
2021-04-28 11:34:06
golang 微服务之gRPC与Protobuf的使用
2023-06-17 20:36:03
Python创建xml文件示例
2023-03-08 22:41:45
mysql 循环批量插入的实例代码详解
2024-01-16 10:28:23