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

【链表OJ题(五)】合并两个有序链表

在这里插入图片描述

​📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:数据结构
🎯长路漫漫浩浩,万事皆有期待

文章目录

  • 链表OJ题(五)
    • 1. 合并两个有序链表
      • 1.1 思路--带哨兵位的头结点
      • 1.2 思路--不强行加头结点
  • 2.总结:

上一篇链表OJ题链接:【链表OJ题(四)】反转链表

链表OJ题(五)

1. 合并两个有序链表

链接:21. 合并两个有序链表

描述:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
在这里插入图片描述

示例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.1 思路–带哨兵位的头结点

之前做过一道题目,叫做合并两个有序数组。其中有一种方法是创建一个新数组,然后遍历两个数组,将两个数组的较小的元素放置到新数组中。一个数组遍历完,将没有放置的元素放置到新数组中,然后拷贝回原数组。

那么这道题能否借鉴它的思路?
合并两个有序链表,链表和数组不同,数组形式的一种方法需要我们创建一个新数组。但是对于链表而言我们可以通过指针改变链接关系,所以不需要创建新链表,只需要修改即可。
有序数组的做法是将较小元素逐个尾插到新数组中,那么我们也可以将较小元素尾插到链表中

那么链表为空如何处理?
这时就又要用到哨兵位(头结点)了,我们给一个哨兵位 head,它也不存储数据,那么不就可以了?但是注意有效数据从 head->next 开始。
在这里插入图片描述

但是尾插存在两个问题,当尾插的时候,我们需要找链表的尾,而且当链表为空时,需要特殊处理。为了避免每次找链表的尾,那么我们就给定一个 tail,这样只要将 tail 迭代就可以。
在这里插入图片描述

注意:哨兵位需要释放,否则会造成内存泄漏。
在这里插入图片描述

代码:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* head = NULL, *tail = NULL;if (list1 == NULL){return list2;} if (list2 == NULL){return list1;}// 哨兵位// 这里 tail 也需要动态开辟一下// 因为不在迭代时进行第一次插入的处理// tail 一开始为空指针,会报错head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));   while (list1 && list2){if (list1->val < list2->val){tail->next = list1; // 当前结点链表的尾链接到 list1tail = list1; // 链表的尾变成 list1list1 = list1->next; // list1 并没有改变,list1 迭代到list1的下一个节点}else{tail->next = list2;tail = list2;list2 = list2->next;}}// 未放置完的元素// 这里和数组的完全不一样// 链表是串联的,所以只需要把当前节点给到tail->next// 就可以全部串联if (list1){tail->next = list1;}if (list2){tail->next = list2;}// 释放哨兵位struct ListNode* ans = head->next;free(head); return ans;
}

在这里插入图片描述

1.2 思路–不强行加头结点

这道题目不使用哨兵位也能写,但是使用这种方法时,需要处理一下链表第一次合并时尾插的情况,大体思路和带哨兵位差不多,但需要注意一下细节

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if (list1 == NULL)return list2;if (list2 == NULL)return list1;struct ListNode *head, *tail;head = tail = NULL;while (list1 && list2){if (list1->val < list2->val){// 第一次合并if (tail == NULL){head = tail = list1;}else{tail->next = list1;tail = tail->next;}list1 = list1->next;}else{// 第一次合并if (tail == NULL){head = tail = list2;}else{tail->next = list2;tail = tail->next;}list2 = list2->next;}}if (list1)tail->next = list1;if (list2)tail->next = list2;return head;
}

在这里插入图片描述

2.总结:

今天我们通过两种思路分析并完成合并两个有序链表这道链表OJ题目,也更加深层次了解和使用了带哨兵位的头结点这个思路,在之后的题目中将再次出现它的使用。希望我的文章和讲解能对大家的学习提供一些帮助。

当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

在这里插入图片描述

相关文章:

【链表OJ题(五)】合并两个有序链表

​ ​&#x1f4dd;个人主页&#xff1a;Sherry的成长之路 &#x1f3e0;学习社区&#xff1a;Sherry的成长之路&#xff08;个人社区&#xff09; &#x1f4d6;专栏链接&#xff1a;数据结构 &#x1f3af;长路漫漫浩浩&#xff0c;万事皆有期待 文章目录链表OJ题(五)1. 合并…...

C++ Primer第五版_第三章习题答案(1~10)

文章目录练习3.1练习3.2一次读入一行一次读入一个词练习3.3练习3.4大的字符串长度大的字符串练习3.5未隔开的隔开的练习3.6练习3.7练习3.8练习3.9练习3.10练习3.1 使用恰当的using 声明重做 1.4.1节和2.6.2节的练习。 // 1.4.1 #include <iostream>using std::cin; using…...

小样本学习

机器学习就是从数据中学习&#xff0c;从而使完成任务的表现越来越好。小样本学习是具有有限监督数据的机器学习。类似的&#xff0c;其他的机器学习定义也都是在机器学习定义的基础上加上不同的限制条件衍生出来。例如&#xff0c;弱监督学习是强调在不完整、不准确、有噪声、…...

python打包成apk界面设计,python打包成安装文件

大家好&#xff0c;给大家分享一下如何将python程序打包成apk文件&#xff0c;很多人还不知道这一点。下面详细解释一下。现在让我们来看看&#xff01; 1、如何用python制作十分秒加减的apk 如何用python制作十分秒加减的apk&#xff1f;用法:. apk包放入apk文件目录,然后输入…...

pytorch转onnx踩坑日记

在深度学习模型部署时&#xff0c;从pytorch转换onnx的过程中&#xff0c;踩了一些坑。本文总结了这些踩坑记录&#xff0c;希望可以帮助其他人。 首先&#xff0c;简单说明一下pytorch转onnx的意义。在pytorch训练出一个深度学习模型后&#xff0c;需要在TensorRT或者openvin…...

极智AI | GPT4来了,ChatGPT又该升级了

欢迎关注我,获取我的更多经验分享 大家好,我是极智视界,本文介绍一下 GPT4来了,ChatGPT又该升级了,更多的是个人思考。 邀您加入我的知识星球「极智视界」,星球内有超多好玩的项目实战源码下载,链接:https://t.zsxq.com/0aiNxERDq 从 ChatGPT 发布 (2022年11月30日) 到…...

智能优化算法之灰狼优化算法(GWO)的实现(Python附源码)

文章目录一、灰狼优化算法的实现思路1、社会等级结构分级2、包围猎物3、攻击猎物4、搜索猎物二、算法步骤三、实例一、灰狼优化算法的实现思路 灰狼优化算法&#xff08;Grey Wolf Optimizer&#xff0c;简称GWO&#xff09;是由Seyedali Mirjalili等人于2014年提出的一种群智…...

leetCode热题10-15 解题代码,思路

前言 计划做一系列算法题的文章&#xff0c;因为自己这块确实比较薄弱&#xff0c;但又很重要&#xff01;写这篇文章前&#xff0c;我已经刷了一本剑指offer&#xff0c;leetcode top150道&#xff0c;牛客某题库106道 这个样子吧&#xff0c;感觉题量算是入门了吧&#xff1…...

同步辐射GISAXS和GIWAXS的原理及应用领域

同步辐射GISAXS和GIWAXS是两种常用的同步辐射X射线衍射技术&#xff0c;它们在材料科学、化学、生物学、物理学等领域中广泛应用。本文将从原理、实验方法和应用三个方面&#xff0c;对同步辐射GISAXS和GIWAXS进行描述和比较。 一、原理 GISAXS和GIWAXS都是利用X射线与样品相互…...

OpManager 进行网络性能管理

计算机网络构成了任何组织的 IT 基础架构的支柱。由于企业严重依赖基于互联网的应用程序&#xff0c;由于网络相关问题&#xff0c;最终用户不受影响非常重要。因此&#xff0c;借助网络管理解决方案监控和提高网络性能对于保持企业始终正常运行至关重要。这将确保维护服务级别…...

面试被问到向上转型和向下转型时,怎么回答?

目录 前置小知识 1、向上转型 补充&#xff1a;向上转型的三种情况 2、向下转型 使用关键字&#xff1a;instanceof 3、转型带来了什么好处 前置小知识 java中的继承&#xff0c;我们简单回顾一下 通过java中的继承机制&#xff0c;可以实现一个类继承另一个类&#xff…...

加密月解密:概述,基础篇

加密月解密&#xff1a;概述&#xff0c;基础篇 2022找工作是学历、能力和运气的超强结合体&#xff0c;遇到寒冬&#xff0c;大厂不招人&#xff0c;可能很多算法学生都得去找开发&#xff0c;测开 测开的话&#xff0c;你就得学数据库&#xff0c;sql&#xff0c;oracle&…...

DC-DC升压模块隔离高压稳压电源直流变换器12v24v48v转600V1000V1100V1500V2000V3000V

特点● 效率高达 80%● 2*2英寸标准封装● 单双电压输出● 价格低● 大于600V高压,稳压输出● 工作温度: -40℃~85℃● 阻燃封装&#xff0c;满足UL94-V0 要求● 温度特性好● 可直接焊在PCB 上应用HRB W1~25W 系列模块电源是一种DC-DC升压变换器。该模块电源的输入电压分为&am…...

pandas数据分析(三)

书接pandas数据分析&#xff08;二&#xff09; 文章目录DataFrame数据处理与分析处理超市交易数据中的异常值处理超市交易数据中的缺失值处理超市交易数据中的重复值使用数据差分查看员工业绩波动情况使用透视表与交叉表查看业绩汇总数据使用重采样技术按时间段查看员工业绩Da…...

cpu performance profiling

精彩文章分享1. android performanceAndroid 性能分析工具介绍 (qq.com)手机Android存储性能优化架构分析 (qq.com)抖音 Android 性能优化系列&#xff1a;启动优化之理论和工具篇 (qq.com)那些年&#xff0c;我们一起经历过的 Android 系统性能优化 (qq.com)Android卡顿&#…...

vue2启动项目npm run dev报错 Error: Cannot find module ‘babel-preset-es2015‘ 修改以及问题原因

报错内容如下图&#xff1a; 说找不到模块 babel-preset-es2015。 在报错之前&#xff0c;我正在修改代码&#xff0c;使用 ElementUI 的按需引入方式&#xff0c;修改了 babel.config.js 。 注意&#xff1a;vue/cli 脚手架4版本已经使用了 babel7 &#xff0c;所以项目中…...

*9 set up 注意点

1、set up 执行的时机&#xff1a;beforeCreate 之前执行一次&#xff0c;this 是 undefined 2、set up 的参数&#xff1a; props&#xff1a;值为对象&#xff0c;组件外传递属性&#xff0c;内部声明并且接收属性 context&#xff1a;上下文对象&#xff0c;其内部包含三个…...

linux目录——文件管理

个人简介&#xff1a;云计算网络运维专业人员&#xff0c;了解运维知识&#xff0c;掌握TCP/IP协议&#xff0c;每天分享网络运维知识与技能。座右铭&#xff1a;海不辞水&#xff0c;故能成其大&#xff1b;山不辞石&#xff0c;故能成其高。个人主页&#xff1a;小李会科技的…...

使用new bing简易教程

申请new bing 首先先申请new bing然后等待通过&#xff0c;如下图 申请完&#xff0c;用edge浏览器&#xff0c;若有科学方法&#xff0c;就能在右上角的聊天进行向AI提问 使用插件来进行直接访问New Bing 在edge浏览器中安装一个插件&#xff0c;地址为&#xff1a;Mod…...

idea插件分享 显著提高开发效率

idea插件 Prettier 作用&#xff1a;支持代码格式化&#xff08;java、js等&#xff09; 另外支持js内方法跳转和js中ajax请求跳转到java代码里面 下载&#xff1a;Prettier SQL Params Setter 作用&#xff1a;将日志中mapper输出preparing和paramters处理成完整可直接执行…...

智能客服意图识别实战:基于AI辅助开发的架构设计与避坑指南

在智能客服系统中&#xff0c;意图识别是决定对话能否顺畅进行的关键。简单来说&#xff0c;它就像客服的“耳朵”和“大脑”&#xff0c;需要准确听懂用户五花八门的问法&#xff0c;并快速判断出用户到底想干什么——是查询订单、投诉问题&#xff0c;还是咨询产品。然而&…...

Delphi 综合实战:整合所有知识点,打造企业级进销存小系统(可直接商用)

前面我们陆续学会了 Delphi 开发的所有核心技能&#xff1a;基础语法、桌面工具、数据库操作、串口通信、网络请求、JSON 解析、Excel 导出、UI 美化、多窗体管理、权限控制。 这一篇&#xff0c;我们将 整合所有知识点&#xff0c;做一个完整的 企业级进销存小系统&#xff0…...

java毕业设计基于springboot西岭雪山智慧景区管理系统

前言 随着旅游业的快速发展和游客数量的不断增加&#xff0c;西岭雪山景区面临着越来越多的管理挑战。传统的景区管理方式往往存在效率低下、信息不透明、游客体验差等问题。为了解决这些困境&#xff0c;基于Spring Boot的西岭雪山智慧景区管理系统应运而生。该系统旨在通过先…...

phpIPAM vs Netbox深度对比:开源IP管理工具选型指南(附GCP云环境部署实录)

phpIPAM vs Netbox深度对比&#xff1a;开源IP管理工具选型指南&#xff08;附GCP云环境部署实录&#xff09; 在数字化转型浪潮中&#xff0c;企业网络基础设施的复杂度呈指数级增长。IP地址作为网络通信的基础要素&#xff0c;其管理效率直接影响运维团队的工作效能。传统Exc…...

嵌入式开发问题复现与调试技巧

嵌入式开发常见问题及解决方法1. 问题复现方法稳定复现问题是解决嵌入式系统故障的首要步骤。根据问题特性&#xff0c;可采用以下三种复现方法&#xff1a;1.1 模拟复现条件对于依赖特定外部条件的问题&#xff0c;最直接的复现方式是精确还原问题发生时的环境参数。工程实践中…...

AlphaFold实战指南:如何利用Colab+开源代码复现蛋白质结构预测(避坑版)

AlphaFold实战指南&#xff1a;如何利用Colab开源代码复现蛋白质结构预测&#xff08;避坑版&#xff09; 蛋白质结构预测一直是计算生物学领域的圣杯级难题。2021年DeepMind发布的AlphaFold2以原子级精度解决了这一挑战&#xff0c;彻底改变了结构生物学的研究范式。本文将带你…...

避开这3个坑!Zynq PS与PL通过BRAM通信时,你的AXI配置可能错了

Zynq PS与PL通过BRAM通信的三大AXI配置陷阱与实战解决方案 在嵌入式系统开发中&#xff0c;Zynq系列芯片的PS&#xff08;Processing System&#xff09;与PL&#xff08;Programmable Logic&#xff09;之间的高效数据交互是许多项目的核心需求。BRAM&#xff08;Block RAM&am…...

『NAS』老破小也能玩 AI?飞牛 NAS 部署 LocalAI

点赞 关注 收藏 学会了 &#x1f4a1;整理了一个 NAS 专属玩法专栏&#xff0c;感兴趣的工友可以戳这里关注 &#x1f449; 《NAS邪修》 LocalAI 是一个开源的"AI壳"&#xff0c;它能让你在自己的硬件上&#xff08;比如 NAS&#xff09;离线运行各种大模型&#…...

从图表示学习到影响力优化:DeepIM框架的端到端革新之路

1. 影响力最大化的技术困局与破局点 社交网络分析领域有个经典问题&#xff1a;给你100个免费试用品&#xff0c;如何选择初始用户才能让产品信息像病毒一样扩散&#xff1f;这就是影响力最大化&#xff08;Influence Maximization&#xff09;问题的现实映射。传统方法就像拿着…...

foobox-cn深度解析:foobar2000高级定制实战指南

foobox-cn深度解析&#xff1a;foobar2000高级定制实战指南 【免费下载链接】foobox-cn DUI 配置 for foobar2000 项目地址: https://gitcode.com/GitHub_Trending/fo/foobox-cn foobar2000作为专业音乐播放器&#xff0c;其默认界面往往难以满足高级用户的个性化需求。…...