leetcode 21:合并两个有序链表 python3解答

el/2024/5/23 0:50:55

题目描述:

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/merge-two-sorted-lists

解答

方法1:不创建新的链表,取一个链表插入另一个链表中
# Definition for singly-linked list.
class ListNode(object):def __init__(self, x):self.val = xself.next = Noneclass Solution(object):def mergeTwoLists(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""if not l1 and not l2:return Noneif not l1:return l2if not l2:return l1while l2:node_temp = ListNode(l2.val) #取出链表l2的一个值,再调用函数插入到l2中l1 = insert_list(l1, node_temp)l2 = l2.nextreturn l1def insert_list(l1, node1):  #可能是头部、中部、尾部插入if node1.val < l1.val:node1.next = l1l1 = node1return l1  #头部插入curnode = l1nextnode = l1.nextwhile nextnode:if node1.val < nextnode.val:node1.next = curnode.nextcurnode.next = node1return l1  #中部插入else:curnode = nextnodenextnode = nextnode.nextcurnode.next = node1  return l1  #尾部插入
方法2:新建一个链表,取两条链表中的最小元素依次插入, 又名迭代
class Solution(object):def mergeTwoLists(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""if not l1 and not l2:return Noneif not l1:return l2if not l2:return l1l3 = ListNode(0)  #使用有头节点的链表curnode = l3while l1 and l2:if l1.val < l2.val:curnode.next = l1l1 = l1.nextelse:curnode.next = l2l2 = l2.nextcurnode = curnode.nextif l1:curnode.next = l1elif l2:curnode.next = l2return l3.next
方法3:递归
class Solution(object):def mergeTwoLists(self, l1, l2):""":type l1: ListNode:type l2: ListNode:rtype: ListNode"""if not l1 and not l2:return Noneif not l1:return l2if not l2:return l1if l1.val < l2.val:pre = l1pre.next = self.mergeTwoLists(l1.next, l2)else:pre = l2pre.next = self.mergeTwoLists(l1, l2.next)return pre

不知道为何,使用递归方法在leetcode编译总是失败,之后再琢磨一下!


http://www.ngui.cc/el/4994716.html

相关文章

leetcode1:两数之和 python3解法

题目描述&#xff1a; 给定一个整数数组 nums 和一个目标值 target&#xff0c;请你在该数组中找出和为目标值的那 两个 整数&#xff0c;并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是&#xff0c;数组中同一个元素不能使用两遍。 例&#xff1a; 给定 …

C++复制构造函数和构造函数调用小困惑

最近看清华大学郑莉老师的C课程&#xff0c;过C的基础知识。遇到了一点小问题。 B站清华大学C课程 在进行类组合例子的调试中&#xff0c;有些不解的地方。先上代码。 #include "pch.h" #include <iostream> using namespace std;class Point { public: …

前置++与后置++区别

对于前置与后置以前只知道它们的两点区别&#xff1a; 1. 前置&#xff1a;先加再用&#xff1b;后置&#xff1a;先用后加。 2. i效率比i效率高&#xff1b; 今日又添加一项&#xff1a; 3. 前置可操作&#xff0c;后置不可操作 只知其果&#xff0c;不明其因非学者姿态。 下…

C++基础(code)

C基础学习&#xff08;code&#xff09; 算是突袭学习吧&#xff0c;可能不是很细。 英语渣&#xff0c;但还是可能会写一些英文注释&#xff0c;提高提高~~ #include <iostream> using namespace std;//函数声明&#xff0c;要么定义在main前,要么在main前面自己添加定…

NEO4J 安裝

NEO4J 安裝 安裝教程&#xff1a; https://blog.csdn.net/sinat_36226553/article/details/108541370 注意事項 不能安裝在 D:\Program Files下&#xff0c;會有不能識別’.ps1’ 拓展名&#xff0c;猜測是不能識別目錄中的空格導致。

Elasticsearch 进阶学习

先上两个学习链接&#xff1a; Elasticsearch学习笔记_KISS-CSDN博客 Elasticsearch API查询_森四杨的博客-CSDN博客 1. es分布式集群 1. 搭建过程 2. 概念 节点、分片&#xff08;Shards&#xff09;、副本(Replicas)、索引、文档、字段、映射对索引中的文档可以进行索引…

python 正则表达式转义上的 r 与反斜杠

先阅读 https://blog.csdn.net/jinixin/article/details/56705284 后举例 转义有两种&#xff1a; 首先是正常的字符串转义&#xff0c;对于特殊的字符进行转义。然后&#xff0c;对于正则表达式还要进行一次转义。 使用原生字符r 可以跳过一次转义。所以在正则表达式前可以…

Python 转义字符和正则表达式的元字符

python转义字符 图片来自 Python 转义字符 \x 正则表达式元字符 正则表达式其他字符

neo4j 关于日期和时间的操作

最近使用neo4j存储数据&#xff0c;其中包含了大量的时间数据&#xff0c;存储的时候都是以字符串的形式存储&#xff0c;如 ‘11:07’&#xff0c;导致后期查询后的数值计算比较困难。中文的这方面笔记似乎比较少&#xff0c;于是记录一下。日期和具体的时间操作类似&#xff…

Lua语言在移动iSO平台上成为新宠

http://www.cwowaddon.com/article-39-1.html Lua最流行的应用场景是在游戏中作为处理逻辑的脚本&#xff0c;即用来编写游戏的任务脚本&#xff0c;以实现游戏的可配置性和可扩展性。在游戏中Lua脚本的加载不需重启服务器&#xff0c;尽管脚本的运行效率低于编译好的二进制代…