leetcode21:合并两个有序列表

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

示例 1:

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

示例 2:

输入:l1 = [], l2 = []
输出:[]

示例 3:

输入:l1 = [], l2 = [0]
输出:[0]

提示:

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

步骤1:问题定义和边界条件分析

问题描述: 我们有两个已经按升序排列的链表,任务是将它们合并成一个新的升序链表并返回。新链表由这两个链表的所有节点拼接而成。

输入输出条件

  • 输入:两个链表 l1l2
    • l1l2ListNode 节点组成,每个节点包含一个整数值和一个指向下一个节点的指针。
    • 链表 l1l2 均按非递减顺序排列。
  • 输出:一个新的链表,该链表由两个输入链表的所有节点组成,并按升序排列。

限制

  • 节点数量范围在 [0, 50] 之间。
  • 节点值范围在 [-100, 100] 之间。

边界条件

  1. l1l2 为空链表的情况。
  2. l1l2 均为空链表。
  3. 所有节点的值相等或完全相反的情况。
  4. l1l2 长度不等。

步骤2:解题思路

问题分解: 这个问题是经典的有序链表合并问题,可以用双指针的方式来高效解决。我们可以依次比较两个链表的当前节点,将较小的节点加入到新链表中,并将对应链表的指针向前移动,直到遍历完两个链表。

算法设计

  1. 创建一个虚拟头节点(dummy node)dummy,用于存放合并后的链表,这样可以简化链表操作。
  2. 使用两个指针 p1p2 指向 l1l2 的当前节点。
  3. 使用指针 curr 作为新链表的构建指针,将较小的节点连接到新链表中:
    • 如果 p1 的值小于等于 p2,将 p1 指向的节点连接到新链表,并移动 p1
    • 否则,将 p2 指向的节点连接到新链表,并移动 p2
  4. 当某个链表遍历完后,将另一个链表剩余的部分直接连接到新链表末尾。
  5. 返回 dummy->next,即合并后的链表。

复杂度分析

  • 时间复杂度:O(m + n),其中 mn 分别是 l1l2 的长度。
  • 空间复杂度:O(1),我们只需常数级空间存储指针变量。

算法设计思路:采用双指针法实现,既高效又能保持原链表的升序性质。


步骤3:详细代码实现

步骤4:算法优化和启发

  1. 链表操作优化:通过虚拟头节点简化链表操作,避免了特殊情况处理,提高了代码的简洁性和可读性。
  2. 双指针效率:该算法利用了双指针法,在每次比较时只移动其中一个指针,提高了时间效率。在合并有序链表或数组等问题中,双指针法非常高效。
  3. 内存优化:由于链表本身是动态数据结构,操作过程中我们直接在原链表上操作,保持了空间利用的最小化。

步骤5:实际应用场景

该算法在实际生活中具有广泛的应用,尤其在数据整合数据流排序等领域非常有效。例如,在实时数据分析中,可能需要将多个数据流按顺序合并并处理。可以参考以下示例:

实际应用示例:股票行情数据流合并

在金融领域,各种股票交易所提供的行情数据流可能会按照时间顺序独立传输。为了向用户显示整体行情变化,往往需要将来自多个交易所的按时间排序的行情数据合并为一个完整的时间序列。

实现方法:

  • 每个交易所的行情数据作为一个按时间升序的链表或流。
  • 使用上述链表合并算法,将各交易所数据按时间顺序合并成一个时间序列,并将结果传输给用户。

这种方法可以确保数据的实时性和有序性,有助于分析师和投资者实时跟踪所有交易所的综合行情信息。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/465574.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

开源模型应用落地-glm模型小试-glm-4-9b-chat-vLLM集成(四)

一、前言 GLM-4是智谱AI团队于2024年1月16日发布的基座大模型&#xff0c;旨在自动理解和规划用户的复杂指令&#xff0c;并能调用网页浏览器。其功能包括数据分析、图表创建、PPT生成等&#xff0c;支持128K的上下文窗口&#xff0c;使其在长文本处理和精度召回方面表现优异&a…

K8S篇(基本介绍)

目录 一、什么是Kubernetes&#xff1f; 二、Kubernetes管理员认证&#xff08;CKA&#xff09; 1. 简介 2. 考试难易程度 3. 考试时长 4. 多少分及格 5. 考试费用 三、Kubernetes整体架构 Master Nodes 四、Kubernetes架构及和核心组件 五、Kubernetes各个组件及功…

关于路由笔记

路由 定义&#xff1a; 在计算机网络中&#xff0c;路由是将数据包从源节点传输到目标节点的过程。这个过程涉及到网络中的多个设备&#xff0c;如路由器、交换机等&#xff0c;其中路由器起着关键的决策作用。 工作原理示例&#xff1a; 假设你在一个公司的局域网内&#…

人工智能之人脸识别(人脸采集人脸识别)

文章目录 前言PySimpleGUI 库1-布局和窗口 前言 例如&#xff1a;随着人工智能的不断发展&#xff0c;本文主要介绍关于人工智能中GUI和PyMysql相应用。 本文采用代码&#xff0b;逻辑思路分析的方式有助于理解代码。 PySimpleGUI 库 PySimpleGUI 是一个用于简化 GUI 编程的…

如何找到养生生活视频素材?推荐几个优秀网站

今天&#xff0c;我们来聊一个实用的话题&#xff0c;那就是如何找到优质的养生视频素材。作为自媒体创作者&#xff0c;高质量的视频素材对内容制作至关重要。不论你是刚入行的新手&#xff0c;还是已经积累了一定粉丝的大V&#xff0c;找到合适的养生视频素材都能帮助你更好地…

旋转对称性,旋转矩阵的特征矢量也是T3矩阵的特征矢量

旋转对称性要求T3矩阵&#xff0c;在旋转后&#xff0c;特征矢量没发生改变&#xff0c;特征值大小也没变&#xff0c;即T3矩阵没有改变

美畅物联丨物联网通信新纪元:Cat.1与5G RedCap的差异化应用

​ 在物联网&#xff08;IoT&#xff09;迅猛发展的时代&#xff0c;通信标准对物联网设备的连接性、性能和适用性有着极为关键的作用。小编在《美畅物联丨Cat.1与NB-IoT&#xff1a;物联网设备的通信标准对比》中提到Cat.1与NB-IoT的对比区别&#xff0c;后来就有小伙伴问&…

OpenCV视觉分析之目标跟踪(12)找到局部的最大值函数meanShift()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在反向投影图像上找到一个对象。 meanShift 是一种用于图像处理和计算机视觉领域的算法&#xff0c;特别适用于目标跟踪、图像分割等任务。该算…

应急救援无人车:用科技守护安全!

一、核心功能 快速进入危险区域&#xff1a; 救援无人车能够迅速进入地震、火灾、洪水等自然灾害或重大事故的现场&#xff0c;这些区域往往对人类救援人员构成极大威胁。 通过自主导航和环境感知技术&#xff0c;无人车能够避开危险区域&#xff0c;确保自身安全的同时&…

安装acondana3, Conda command not found

Linux 服务器安装acondana3后 输入conda找不到 写入路径也没找到 vim ~/.bashrc 加入 PATH"root/anaconda3/bin:$PATH" 更新文件&#xff1a; source ~/.bashrc 还是找不到conda 命令 解决办法 source ~/anaconda3/etc/profile.d/conda.sh conda activate Your_e…

第07章 运算符的使用

一、算数运算符 算术运算符主要用于数学运算&#xff0c;其可以连接运算符前后的两个数值或表达式&#xff0c;对数值或表达式进行加 &#xff08;&#xff09;、减&#xff08;-&#xff09;、乘&#xff08;*&#xff09;、除&#xff08;/&#xff09;和取模&#xff08;%&a…

6堆(超级重点)

堆&#xff08;Heap&#xff09;的核心概述 堆针对一个 JVM 进程来说是唯一的&#xff0c;也就是一个进程只有一个 JVM&#xff0c;但是进程包含多个线程&#xff0c;他们是共享同一堆空间的。 6.1.1. 堆内存细分 Java 7 及之前堆内存逻辑上分为三部分&#xff1a;新生区养老…

Google Guava 发布订阅模式/生产消费者模式 使用详情

目录 Guava 介绍 应用场景举例 1. 引入 Maven 依赖 2. 自定义 Event 事件类 3. 定义 EventListener 事件订阅者 4. 定义 EventBus 事件总线 5. 定义 Controller 进行测试 Guava 介绍 Guava 是一组来自 Google 的核心 Java 库&#xff0c;里面包括新的集合 类型&#xff08…

全面解析:网络协议及其应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 # 全面解析&#xff1a;网络协议及其应用 文章目录 网络协议概述定义发展历程主要优势 主要网络协议应用层协议传输层协议网络层…

如何使用SSH密钥和公钥加密技术保护您的cPanel服务器

在服务器管理过程中&#xff0c;cPanel和WHM是我们常用的管理工具。然而&#xff0c;有时我们仍然需要直接登录到服务器的Shell环境&#xff0c;以便执行脚本或修改配置文件。使用SSH是最安全的远程登录方式。SSH是一种安全协议&#xff0c;它能够加密你向服务器发送的命令以及…

【前端】JSX 中的 Fragments 详解

在 React 和 JSX 中&#xff0c;Fragments 是一个非常有用的概念&#xff0c;用于在不引入额外 DOM 节点的情况下返回多个元素。Fragments 可以帮助你保持 DOM 结构的整洁&#xff0c;避免不必要的嵌套层级。本文将详细介绍 Fragments 的概念、用法以及其在实际开发中的应用场景…

mac单独打开QT帮助文档助手

mac单独打开QT帮助文档助手 1.概述 windows和mac查看QT帮助文档的路径不同&#xff0c;下面给出两个系统的查找路径。 Windows 下&#xff1a; C:\Qt\Qt5.9.9\5.9.9\mingw49_32\bin\assistant.exeMac 下&#xff1a; /Users/apple/Qt5.9.9/5.9.9/clang_64/bin/Assistant2.使…

SSLHandshakeException错误解决方案

1、错误提示 调用Http工具报如下异常信息&#xff1a; cn.hutool.core.io.IORuntimeException: SSLHandshakeException: Received fatal alert: handshake_failure2、查询问题 一开始我以为是代码bug&#xff0c;网络bug甚至是配置环境未生效&#xff0c;找了一大圈&#xf…

海量数据迁移:Elasticsearch到OpenSearch的无缝迁移策略与实践

文章目录 一&#xff0e;迁移背景二&#xff0e;迁移分析三&#xff0e;方案制定3.1 使用工具迁移3.2 脚本迁移 四&#xff0e;方案建议 一&#xff0e;迁移背景 目前有两个es集群&#xff0c;版本为5.2.2和7.16.0&#xff0c;总数据量为700T。迁移过程需要不停服务迁移&#…

【IEEE出版】第六届国际科技创新学术交流大会暨信息技术与计算机应用学术会议(ITCA 2024,12月06-08)

第六届国际科技创新学术交流大会暨信息技术与计算机应用学术会议&#xff08;ITCA 2024) 2024 6th International Conference on Information Technology and Computer Application 会议官网&#xff1a;itca2024.iaecst.org 会议时间&#xff1a;2024年12月06-08日 截稿时…