LeetCode 21:合并两个有序链表 Merge Two Sorted Lists
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
示例:
输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4
解题思路:
迭代和递归都能解题。无非是依次将两个链表每个节点的值对比,取出值较小的节点,添加到新链表末尾。然后继续比较两个链表,直到其中一个链表遍历完成,此时另一个链表剩余所有节点直接添加到新链表之后即可。其逻辑为:
原链表:1->2->4->null,1->3->4->5->6->null
依次对比节点值,取出各自头节点:1 = 1
值相同取出一个节点 1,组成新链表:1
此时原链表:2->4->null,1->3->4->5->6->null对比头节点值:2 > 1
取出 1 节点,添加到新链表末尾:1->1
此时原链表:2->4->null,3->4->5->6->null对比头节点值:2 < 3
取出 2 节点,添加到新链表末尾:1->1->2
此时原链表:4->null,3->4->5->6->null.......依次类推,直到其中一个原链表为空时:
原链表:null,4->5->6->null
新链表:1->1->2->3->4
这时其中一个原链表已经为空,则直接将另一个原链表添加到新链表末尾即可:
1->1->2->3->4->4->5->6->null
迭代法:
迭代法需要注意:先判断原链表是否为空;对比原链表第一个节点值的大小,选择较小一个作为新链表的头节点。之后才能按上述逻辑执行。
如果添加一个虚拟节点作为头节点,则无需上述条件,但应当返回虚拟节点的下一个节点。
Java:
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode head = new ListNode(-1);//新建虚拟头节点 ListNode cur = head;//当前节点指向虚拟头节点 while (l1 != null && l2 != null) {//循环条件为链表都不为空 if (l1.val < l2.val) {//比较头节点的值的大小 cur.next = l1;//当前节点连接到节点值较小的一个 l1 = l1.next;//刷新原链表头节点 cur = cur.next;//刷新当前节点 } else { cur.next = l2; l2 = l2.next; cur = cur.next; } } if (l1 == null) cur.next = l2;//选择另外一个不为空的原链表,连接到新链表末尾 else cur.next = l1; return head.next;//返回虚拟头节点的下一个节点,即真实头节点 } }
Python3:
class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: head = ListNode(-1) cur = head; while l1 and l2: if l1.val <= l2.val: cur.next = l1 cur = cur.next l1 = l1.next else: cur.next = l2 cur = cur.next l2 = l2.next if l1: cur.next = l1 else: cur.next = l2 return head.next
递归法:
递归基线条件为:原链表其中之一遇到空节点。返回值为:另一个链表剩余部分的头节点。
递归判断头节点的值的大小,取小的节点添加到新链表之后。将剩余链表传回递归函数。
Java:
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2;//基线条件 if (l2 == null) return l1;//基线条件 ListNode head; if (l1.val <= l2.val) {//选择节点值较小的节点 head = l1;//刷新头节点 head.next = mergeTwoLists(l1.next, l2);//剩余链表作为参数传入递归函数 } else { head = l2; head.next = mergeTwoLists(l1, l2.next); } return head; } }
Python3:
class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: if not l1: return l2 if not l2: return l1 if l1.val <= l2.val: head = l1 head.next = self.mergeTwoLists(l1.next, l2) else: head = l2 head.next = self.mergeTwoLists(l1, l2.next) return head
欢迎关注公.众号:爱写Bug
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Fundebug录屏插件更新至0.5.0,新增domain参数
摘要: 通过配置domain来保证“视频”的正确录制 录屏功能介绍 Fundebug提供专业的异常监控服务,当线上应用出现 BUG 的时候,我们可以第一时间报警,帮助开发者及时发现 BUG,提高 Debug 效率。在网页端,我们通过原创的录屏技术,可以 100%还原 BUG 出现之前用户的操作流程,帮助开发者快速复现出错场景。点击查看演示视频。 其实,我们录制的并不是一个真正的视频!算法经过优化,整个“录制”过程 CPU 的使用率非常低。和传统的视频相比,体积小了成百上千倍。Fundebug 插件“录制”的“短视频”,压缩后的体积只有几十 KB。 尊重用户隐私 录屏功能涉及到用户隐私,我们作为第三方服务,也非常重视这一点: Fundebug 默认关闭录屏功能,开发者需要的时候可以自行开启; Fundebug 并不是全程录屏,只会录制 BUG 出现之前 10~20s 的用户操作; Fundebug 提供敏感信息过滤过滤功能,开发者可以过滤掉用户隐私信息; Fundebug 重视数据安全,传输过程全程加密,数据库有多重安全防护; Fundebug 会定期(目前是删除 60 天之前的数据)删...
- 下一篇
Spring 框架文档之 Web —— Servlet 技术栈
Spring Web MVC DispatcherServlet 使用 Java 配置或 web.xml 根据 Servlet 规范进行声明和映射。 然后使用 Spring 配置来发现请求映射、视图解析、异常处理等所需的委托组件。 Servlet 配置 public class MyWebApplicationInitializer implements WebApplicationInitializer { @Override public void onStartup(ServletContext servletCxt) { // Load Spring web application configuration AnnotationConfigWebApplicationContext ac = new AnnotationConfigWebApplicationContext(); ac.register(AppConfig.class); ac.refresh(); // 注册并初始化 DispatcherServlet DispatcherServlet servlet =...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- CentOS6,CentOS7官方镜像安装Oracle11G
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS8编译安装MySQL8.0.19
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Windows10,CentOS7,CentOS8安装MongoDB4.0.16
- CentOS7安装Docker,走上虚拟化容器引擎之路
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题