当前位置: 首页 > news >正文

做网站不会框架/百度贴吧官网首页

做网站不会框架,百度贴吧官网首页,网站如何做等级保护,做网站兴趣爱好😀前言 在算法面试中,链表问题是经常遇到的考点之一,其中合并两个排序链表是一个非常经典的问题。本文将详细介绍如何通过递归和迭代两种方式实现两个有序链表的合并。 🏠个人主页:尘觉主页 文章目录 😀合并…

img

😀前言
在算法面试中,链表问题是经常遇到的考点之一,其中合并两个排序链表是一个非常经典的问题。本文将详细介绍如何通过递归和迭代两种方式实现两个有序链表的合并。

🏠个人主页:尘觉主页

文章目录

  • 😀合并两个排序的链表
    • 😉题目描述
      • 示例1
      • 示例2
      • 示例3
    • 🤔解题思路
      • 🥰递归解法
        • 递归解法的分析
      • 🥰迭代解法
        • 迭代解法的分析
    • 😄总结

😀合并两个排序的链表

NowCoder

😉题目描述

输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围: 0≤n≤1000,−1000≤节点值≤1000
要求:空间复杂度 O(1),时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时,合并后的链表为{1,2,3,4,5,6},所以对应的输出为{1,2,3,4,5,6},转换过程如下图所示:

img

或输入{-1,2,4},{1,3,4}时,合并后的链表为{-1,1,2,3,4,4},所以对应的输出为{-1,1,2,3,4,4},转换过程如下图所示:

img

示例1

  • 输入{1,3,5}{2,4,6}
  • 输出{1,2,3,4,5,6}

示例2

  • 输入{}{}
  • 输出{}

示例3

  • 输入{-1,2,4}{1,3,4}
  • 输出{-1,1,2,3,4,4}

🤔解题思路

要实现两个排序链表的合并,可以使用递归和迭代两种方法。下面分别详细讲解这两种方法的实现思路和代码。

🥰递归解法

递归解法的核心思想是比较两个链表的头节点值,并通过递归调用合并剩余部分的链表。具体而言:

  1. 如果 list1 的头节点值小于等于 list2 的头节点值,则 list1 的头节点应成为新链表的头节点,并递归合并 list1 的剩余部分和 list2
  2. 反之,则 list2 的头节点成为新链表的头节点,并递归合并 list1list2 的剩余部分。

递归解法的代码实现如下:

public ListNode Merge(ListNode list1, ListNode list2) {if (list1 == null)return list2;if (list2 == null)return list1;if (list1.val <= list2.val) {list1.next = Merge(list1.next, list2);return list1;} else {list2.next = Merge(list1, list2.next);return list2;}
}
递归解法的分析
  • 时间复杂度O(n)。每次递归都会遍历一个节点,最终遍历完所有节点,因此时间复杂度为 O(n)
  • 空间复杂度O(n)。由于递归调用占用了系统栈空间,递归深度为 n,空间复杂度为 O(n),不满足题目对 O(1) 空间复杂度的要求。

虽然递归解法简单直观,但在处理深度较大的链表时,可能会出现栈溢出的风险,因此在实际应用中通常更倾向于使用迭代解法。

🥰迭代解法

迭代解法通过维护一个指针逐步遍历两个链表,并根据节点值的大小将节点连接到新链表的末尾。具体实现步骤如下:

  1. 创建一个虚拟头节点 head,用于存储合并后的链表。
  2. 使用 cur 指针遍历 list1list2,将较小值的节点链接到 cur 后面,然后移动 cur 和相应链表的指针。
  3. 如果一个链表遍历完了,直接将另一个链表剩余部分链接到 cur 后面。
  4. 最后返回 head.next,即合并后的链表的头节点。

迭代解法的代码实现如下:

public ListNode Merge(ListNode list1, ListNode list2) {ListNode head = new ListNode(-1);ListNode cur = head;while (list1 != null && list2 != null) {if (list1.val <= list2.val) {cur.next = list1;list1 = list1.next;} else {cur.next = list2;list2 = list2.next;}cur = cur.next;}if (list1 != null)cur.next = list1;if (list2 != null)cur.next = list2;return head.next;
}
迭代解法的分析
  • 时间复杂度O(n)。同样,迭代过程中会遍历所有节点,因此时间复杂度为 O(n)
  • 空间复杂度O(1)。只使用了常量级别的额外空间,满足题目对 O(1) 空间复杂度的要求。

迭代解法不仅在时间和空间复杂度上更加符合题目的要求,还避免了递归深度过大的问题,因此在实际开发中更为常用。

😄总结

合并两个排序链表问题通过递归和迭代两种方法均可以有效解决。递归解法简单直观,但在空间复杂度上有所不足;迭代解法在时间和空间效率上更为优越,是实际应用中的首选方案。

希望通过本文的详细讲解,大家能够掌握这两种合并排序链表的技巧,并在算法面试或实际开发中灵活运用。

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

img

相关文章:

算法的学习笔记—合并两个排序的链表(牛客JZ25)

&#x1f600;前言 在算法面试中&#xff0c;链表问题是经常遇到的考点之一&#xff0c;其中合并两个排序链表是一个非常经典的问题。本文将详细介绍如何通过递归和迭代两种方式实现两个有序链表的合并。 &#x1f3e0;个人主页&#xff1a;尘觉主页 文章目录 &#x1f600;合并…...

《虚拟之旅:开启无限可能的机器世界》简介:

1.Ubonto的介绍&#xff1a; Ubuntu 是一个流行的开源操作系统&#xff0c;基于 Linux 内核。 它具有以下一些特点和优势&#xff1a; 开源免费&#xff1a;任何人都可以免费使用、修改和分发。丰富的软件库&#xff1a;通过软件包管理器可以方便地安装各种应用程序。良好的…...

centos7 服务器搭建

1. 查看 centos 版本 cat /etc/redhat-release CentOS Linux release 7.9.2009 (Core)2 .查看 ip地址 ip addr sudo yum install net-tools -y 3. 是否能够上网 ping www.baidu.com ping 114.114.114.114 sudo systemctl restart network 4. DNS 更新DNS配置 编辑/etc/r…...

【Godot4自学手册】第四十五节用着色器(shader)制作水中效果

本节内容&#xff0c;主要学习利用着色器制作水波纹效果&#xff0c;效果如下&#xff1a; 一、搭建新的场景 首先我们新建场景&#xff0c;根节点选择Node2D&#xff0c;命名为Water&#xff0c;给根节点添加两个Tilemap节点&#xff0c;一个命名为Background主要用于绘制地…...

VMware Workstation Pro 安装 Ubuntu Server

这里写目录标题 VMware Workstation Pro 安装 Ubuntu Server1. 启动选项2. 系统语言3. 安装程序升级4. 键盘配置5. 安装类型6. 网卡配置7. 代理配置8. 系统镜像配置9. 硬盘配置10. 账户配置11. Ubuntu Pro 版本12. SSH 服务13. 推荐软件14. 安装成功15. 第一次重启报错16. 登录…...

智能化包括自动化与非自动化

智能化通常指的是系统或设备具备智能功能&#xff0c;以提高其自主性和效率。智能化可以分为自动化与非自动化两大类&#xff0c;每一类都有其独特的特点和应用场景。 一、自动化 自动化指的是系统能够在无需人为干预的情况下完成任务或操作。自动化系统通常依赖于预设的规则、…...

微前端架构的容器化部署:策略、实践与优势

随着微服务架构的兴起&#xff0c;微前端架构也成为现代Web应用开发的热门趋势。容器化技术&#xff0c;以其轻量级、可移植性和易于管理的特点&#xff0c;成为微前端部署的理想选择。本文将详细介绍微前端架构下应用容器化部署的策略、实践步骤以及这一方法的优势。 容器化技…...

面试题(网络、js、框架)

自我介绍 您好&#xff0c;面试官&#xff01;我叫[您的姓名]&#xff0c;非常荣幸能有机会参加这次面试。 在过去的 3 年里&#xff0c;我一直专注于前端开发领域&#xff0c;积累了丰富的实践经验。 在 Vue.js 项目中&#xff0c;我能够熟练运用组件化开发模式&#xff0c;实…...

C语言典型例题40

《C程序设计教程&#xff08;第四版&#xff09;——谭浩强》 题目 例题3.8 运输公司对用户计算运费。路程&#xff08;以s表示&#xff0c;单位为千米&#xff09;&#xff0c;吨/千米运费越低。标准如下&#xff1a; s<250 没…...

【大模型部署及其应用 】使用 Ollama 和 Ollama WebUI 在本地运行 Llama 3

使用 Ollama 和 Ollama WebUI 在本地运行 Llama 3 目录 开始使用 Llama 3设置 Ollama WebUI访问 Ollama WebUI使用 Docker GenAI Stack 的 Llama 3骆驼 2 与 骆驼 3...

uniapp-部分文件中文乱码

一、问题 在开发时遇到&#xff0c;部分页面的中文显示乱码&#xff0c;如图 搜索了一下解决方法&#xff0c;这里记录一下 二、问题原因&#xff1a; 页面的编码格式不是 utf-8 造成的 三、解决方法 打开出现乱码页面选择编译器左上角的文件 > 以指定编码重新打开 选择U…...

Day41 | 647. 回文子串 516.最长回文子序列

语言 Java 647. 回文子串 回文子串 题目 给你一个字符串 s &#xff0c;请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 思路 动规五部曲来分析 1.dp数组的含义&#x…...

全面解析Gerapy分布式部署:从环境搭建到定时任务,避开Crawlab的坑

Gerapy分布式部署 搭建远程服务器的环境 装好带docker服务的系统 Docker:容器可生成镜像&#xff0c;也可拉去镜像生成容器 示例&#xff1a;将一个环境打包上传到云端(远程服务器)&#xff0c;其他8个服务器需要这个环境直接向云端拉取镜像生成容器,进而使用该环境,比如有MYS…...

Springboot项目中使用druid实现多数据源和动态数据源,因数据库不可用导致的项目挂起的处理方案

Springboot项目中使用druid因数据库不可用导致的项目挂起的处理方案 在Spring Boot项目中使用Druid实现多数据源和动态数据源管理是一个常见的场景。通过合理的配置和错误处理机制&#xff0c;您可以有效地管理数据源&#xff0c;避免因数据库不可用而导致整个项目挂起。 1.…...

多线程 03:知识补充,静态代理与 Lambda 表达式的相关介绍,及其在多线程方面的应用

一、概述 记录时间 [2024-08-16] 前置知识&#xff1a;Java 基础篇&#xff1b;Java 面向对象 多线程 01&#xff1a;Java 多线程学习导航&#xff0c;线程简介&#xff0c;线程相关概念的整理 多线程 02&#xff1a;线程实现&#xff0c;创建线程的三种方式&#xff0c;通过多…...

机器学习中的距离概念

距离在机器学习中应用广泛&#xff0c;包括欧式距离、曼哈顿距离、内积距离和KL距离。 下面总结一下。 机器学习中的距离 欧式距离曼哈顿距离内积距离KL距离距离作为损失函数(MSE/MAE...)欧式距离与内积距离的联系☆距离的有效性 欧式距离 欧式距离&#xff08;Euclidean Dis…...

Java 如何判断map为null或者空

1.示例一 在Java中&#xff0c;如果我们想判断一个Map是否为null或者空&#xff08;即没有任何键值对&#xff09;&#xff0c;我们可以使用以下的方法。下面是一个完整的示例代码&#xff0c;展示了如何进行这样的判断&#xff1a; import java.util.HashMap; import java…...

终端用户视角下的性能测试,体验与度量的融合

传统的性能测试的度量标准是什么 响应时间&#xff08;Response Time&#xff09;&#xff1a; 这是从客户端发出请求到接收到完整响应所需的时间。响应时间是衡量系统性能的重要指标&#xff0c;特别是在面向用户的应用中&#xff0c;因为它直接影响用户体验。 而用户体验的度…...

KCP源码解析系列(二)KCP协议结构体

一、KCP协议包 1.1 kcp协议包 kcp中只有一种数据包&#xff0c;不管是数据还是控制信息&#xff0c;都用这个数据包来表示 0 4 5 6 8 (BYTE) ---------------------------- | conv |cmd|frg| wnd | ---------------------------- 8 | …...

微软运行库全集合:一站式解决兼容性问题

开发者在部署应用程序时经常遇到因缺少运行库而引发的兼容性问题。为了解决这一问题&#xff0c;电脑天空推荐微软常用运行库合集&#xff0c;一个集成了微软多个关键运行库组件的软件包。 &#x1f4da; 包含组件概览&#xff1a; Visual Basic Virtual Machine&#xff1a;…...

【 亿邦动力网-注册安全分析报告】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞 …...

算法笔记|Day26贪心算法IV

算法笔记|Day26贪心算法IV ☆☆☆☆☆leetcode 452. 用最少数量的箭引爆气球题目分析代码 ☆☆☆☆☆leetcode 435. 无重叠区间题目分析代码 ☆☆☆☆☆leetcode 763.划分字母区间题目分析代码 ☆☆☆☆☆leetcode 452. 用最少数量的箭引爆气球 题目链接&#xff1a;leetcode …...

CVPR2023《DNF: Decouple and Feedback Network for Seeing in the Dark》暗光图像增强论文阅读笔记

相关链接 论文链接 https://openaccess.thecvf.com/content/CVPR2023/papers/Jin_DNF_Decouple_and_Feedback_Network_for_Seeing_in_the_Dark_CVPR_2023_paper.pdf 代码链接 https://github.com/Srameo/DNF 摘要 RAW数据的独特属性在低光照图像增强方面展现出巨大潜力。…...

大厂进阶七:React状态管理全解析

前言&#xff1a; React 中用于状态管理的hook及库有&#xff1a;useState、useReducer、useContext、useReducer useContext和一些第三方的库如redux、mobx等。 1、useState 单一组件某个具体状态 2、useReducer 单一组件中多个状态管理&#xff0c;策略分发机制统一管理…...

【ocr识别003】flask+paddleocr+bootstrap搭建OCR文本推理WEB服务

1.欢迎点赞、关注、批评、指正&#xff0c;互三走起来&#xff0c;小手动起来&#xff01; 2.了解、学习OCR相关技术知识领域&#xff0c;结合日常的场景进行测试、总结。如本文总结的flaskpaddleocrbootstrap搭建OCR文本推理WEB服务应用示例场景。 文章目录 1.代码结构2.效果演…...

从零开始搭建 LVS 高性能集群 (DR模式)

从零开始搭建 LVS 高性能集群 &#xff08;DR模式&#xff09; 架构 本设计方案采用三台服务器构建集群&#xff0c;使用Linux Virtual Server (LVS) 作为负载均衡器&#xff0c;运行在直接路由 (DR) 模式下。集群中的每一台服务器都将运行相同的服务&#xff0c;以实现 高可用…...

Linux环境开发工具【yum与vim】

&#x1f308;个人主页&#xff1a;Yui_ &#x1f308;Linux专栏&#xff1a;Linux &#x1f308;C语言笔记专栏&#xff1a;C语言笔记 &#x1f308;数据结构专栏&#xff1a;数据结构 文章目录 1.Linux软件包管理器yum1.1 快速使用yum 2. Linux编辑器-vim的使用2.1 vim的基本…...

laravel GuzzleHttp Client 无法获取返回的错误信息

Client发送一些请求&#xff0c;当返回状态不是200的时候&#xff0c;无法获取完整错误信息 $client new Client([base_uri > $this->getUri()./order/aaaaaa,timeout > 30,verify > false]);try {$response $client->request(POST, , [headers > [Lang&g…...

XMOS 多路音频解码器

当谈及高性能音频解码器&#xff0c;XMOS 是一个不容忽视的名字。作为音频解决方案领域的领军者&#xff0c;XMOS 的多路音频解码器在音频处理技术中扮演着至关重要的角色。下面我们一起深入探讨 XMOS 多路音频解码器去了解这一技术的魅力。 设计背景&#xff1a;追求音频极致…...

XSS小游戏(题目+解析)

xss题目练习地址&#xff1a; xss小游戏 游戏界面 一、Ma Spaghet! 我将题目要求进行翻译: 题目的主要要求就是&#xff1a;弹出一个&#xff08;1337&#xff09;的弹窗 开始解题&#xff1a; Let’s Go! 首先&#xff0c;传个参数看看 发现参数直接显示在了 < h2 >…...