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

参考：合并两个有序链表

到此这篇关于python实现合并两个有序列表的示例代码的文章就介绍到这了,更多相关python 合并两个有序列表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • python 列表元素左右循环移动 的多种解决方案

    python 列表元素左右循环移动 的多种解决方案

    如下所示: #待处理列表 A= [1,2,3,4,5] #移动次数 a = 3 右移比较简单 for i in range(a): A.insert(0,A.pop()) 左移 for i in range(a): A.insert(len(A),A[0]) A.remove(A[0]) #左移 for i in range(a): b = A.pop(0) A.append(b) 列表双向队列 from collections import deque aa = deque(A) #正数表示向

  • 浅谈Python列表嵌套字典转化的问题

    浅谈Python列表嵌套字典转化的问题

    在看视频教程的时候提到了[{'a' : 97}, {'b' : 98}, {'c' : 99}, {'d' : 100}, {'e' : 101}, ...........]形式的列表嵌套形式, 要求是将上述列表转换为{'a' : 97,'b' : 98,'c' : 99 ,'d' : 100,'e' : 101,.....}的字典形式 首先上述的a--->97, b--->98,.....意思是key为a到z的英文小写字母,value值为对应的ascii码, 那么一开始可以结合range()

  • Python基础详解之列表复制

    Python基础详解之列表复制

    一.前言 Python中列表的复制分为几种情况: 直接赋值 浅复制 深复制 下面通过实例分析一下这几种情况的区别. 二.直接赋值 a = [11, 22, 33] b = a print(id(a), id(b)) b[0]=1 print(a,b) 输出结果为如下所示,发现内存地址没有发生变化,b只是a的引用,通过b更改列表的值时,a同时做修改. 三.用切片赋值 a = [11, 22, 33] b = a[:] print(id(a), id(b)) b[0]=1 print(a,b) 输出

  • 浅谈Python基础之列表那些事儿

    浅谈Python基础之列表那些事儿

    一.列表的格式 二.列表的相关操作("增"."删"."改","查") <1> 添加元素 append()通过append可以向列表添加元素. 例: 运行结果: <2> 修改元素("改") 修改元素的时候,要通过下标来确定要修改的是哪个元素,然后才能进行修改. 例: 结果: <3> 查找元素("查"in, not in, index, count) py

  • python中必会的四大高级数据类型（字符,元组,列表,字典）

    python中必会的四大高级数据类型（字符,元组,列表,字典）

    一. 字符串 生活中我们经常坐大巴车,每个座位一个编号,一个位置对应一个下标. 字符串中也有下标,要取出字符串中的部分数据,可以用下标取. python中使用切片来截取字符串其中的一段内容,切片截取的内容不包含结束下标对应的数据. 切片使用语法:[起始下标:结束下标:步长] ,步长指的是隔几个下标获取一个字符. 注意:下标会越界,切片不会 常用函数 练习: Test='rodma ' print(type(Test)) print('Test的一个字符串%s'%Test[0])#跟数组差不多 #

  • Python列表删除重复元素与图像相似度判断及删除实例代码

    Python列表删除重复元素与图像相似度判断及删除实例代码

    发现问题 项目需要,需要删除文件夹中的冗余图片.涉及图像文件名的操作,图像文件名存储在list中 python list删除元素有remove()和pop(),remove()对元素进行操作,pop()对索引进行操作,并会返回pop掉的值.一个只会从列表移除一个数 一.如果已经有了一个列表l,令h=l,对l操作时同时会影响h,貌似原因是内存共享的,正确的方法是h=l.copy() 二.测试时,发现一个问题,如下面代码和结果: item=2时,并没有把2全部删掉,后面重复的3也没有删去. **查阅

  • Python随机函数random随机获取数字、字符串、列表等使用详解

    在python中用于生成随机数的模块是random,在使用前需要import, 下面看下它的用法. Python随机生成一个浮点数 random.random random.random()用于生成一个0到1的随机符点数: 0 <= n < 1.0 注意: 以下代码在Python3.5下测试通过, python2版本可稍加修改 描述 random() 方法返回随机生成的一个实数,它在(0,1)范围内. 语法 以下是 random() 方法的语法: import random random.ra

  • Python 统计列表中重复元素的个数并返回其索引值的实现方法

    Python 统计列表中重复元素的个数并返回其索引值的实现方法

    需求:统计列表list1中元素3的个数,并返回每个元素的索引 list1 = [3, 3, 8, 9, 2, 10, 6, 2, 8, 3, 4, 5, 5, 4, 1, 5, 9, 7, 10, 2] 在实际工程中,可能会遇到以上需求,统计元素个数使用list.count()方法即可,不做多余说明 返回每个元素的索引需要做一些转换,简单整理了几个实现方法 1 list.index()方法 list.index()方法返回列表中首个元素的索引,当有重复元素时,可以通过更改index()方法__s

  • Python列表排序方法reverse、sort、sorted详解

    python语言中的列表排序方法有3个: reverse反转/倒序排序 sort正序排序 sorted可以获取排序后的列表 在更高级列表排序中,后两中方法还可以加入条件参数进行排序. reverse()方法 将列表中元素反转排序,比如下面这样 >>> x = [1,5,2,3,4] >>> x.reverse() >>> x [4, 3, 2, 5, 1] reverse列表反转排序:是把原列表中的元素顺序从左至右的重新存放,而不会对列表中的参数进行排

  • python 合并列表的八种方法

    Python 语言里有许多(而且是越来越多)的高级特性,是 Python 发烧友们非常喜欢的.在这些人的眼里,能够写出那些一般开发者看不懂的高级特性,就是高手,就是大神. 但你要知道,在团队合作里,炫技是大忌. 为什么这么说呢?我说下自己的看法: 越简洁的代码,越清晰的逻辑,就越不容易出错: 在团队合作中,你的代码不只有你在维护,降低别人的阅读/理解代码逻辑的成本是一个良好的品德 简单的代码,只会用到最基本的语法糖,复杂的高级特性,会有更多的依赖(如语言的版本) 1. 最直观的相加 使用 + 对

  • Python统计列表元素出现次数的方法示例

    1. 引言 在使用Python的时候,通常会出现如下场景: array = [1, 2, 3, 3, 2, 1, 0, 2] 获取array中元素的出现次数 比如,上述列表中:0出现了1次,1出现了2次,2出现了3次,3出现了2次. 本文阐述了Python获取元素出现次数的几种方法.点击获取完整代码. 2. 方法 获取元素出现次数的方法较多,这里我提出如下5个方法,谨供参考.下面的代码,传入的参数均为 array = [1, 2, 3, 3, 2, 1, 0, 2] 2.1 Counter方法

  • Python3 列表list合并的4种方法

    下面是列表合并的4种方法,其中的代码都在Python3下测试通过,在Python2下运行应该也没问题,时间关系就没测试,遇到问题可以联系小编 方法1: 直接使用"+"号合并列表 aList = [1,2,3] bList = ['www', 'jb51.net'] cList = aList + bList dList = bList + aList print(cList) print(dList) 输出为: [1, 2, 3, 'www', 'jb51.net'] ['www',

  • Python列表排序 list.sort方法和内置函数sorted用法

    很多时候我们获取到一个列表后,这个列表并不满足我们的需求,我们需要的是一个有特殊顺序的列表. 这时候就可以使用list.sort方法和内置函数sorted,本文就是介绍list.sort方法和sorted内置函数的使用方法和区别. 一.list.sort方法 list.sort方法会就地排序列表,也就是说不会把原列表复制一份.这也是这个方法的返回值是None的原因,提醒您本方法不会新建一个列表. 在这种情况下返回None其实是Python的一个惯例:如果一个函数或者方法对对象进行的是就地改动,那

  • python获取指定时间段内特定规律的日期列表

    python获取指定时间段内特定规律的日期列表

    前言:写小程序时,遇到个需要自定义回归时间的场景,下面是实现的效果图. 于我需求而言,我只需要用到fixed_interval.weekly.per_month三个方法返回的回归间隔列表就行,最后的这个make_date_from_list方法,是为了能在这里展示效果 TIP:没有做异常处理,以及时间格式化之类的.这里只是抛砖引玉给个原型砖头出来. 实现代码: class GetStrategyDedail: today = datetime.date.today() def __init__(

  • Python 把两层列表展开平铺成一层(5种实现方式)

    这几天和同事在讨论,如何用 Python 写出优雅的让列表中的列表展开,变成扁平化的列表. 例如 # 期望输入 input = [[('A', 1), ('B', 2)], [('C', 3), ('D', 4)]] # 期望输出 output = [('A', 1), ('B', 2), ('C', 3), ('D', 4)] map 函数合并 >>> new = []; map(new.extend, input); new [None, None] [('A', 1), ('B',

  • python求列表对应元素的乘积和的实现

    那天偶尔看到看到一个小问题:两个不等长列表a=[1,2,3],b=[4,5,6,7],求它们对应元素的乘积的和. 我一开始想到的方法就是选择更小数组作为循环长度然后相乘求和: a = [1,2,3] b = [4,5,6,7] sum = 0 for i in range(0,min(len(a),len(b))): number += a[i]*b[i] print(sum) 但是后来我想到了一种更为巧妙的方法,利用函数zip(): a = [1,2,3] b = [4,5,6,7] all

随机推荐