合并两个有序链表

问题描述:

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

示例 1:

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

示例 2:

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

示例 3:

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

思路:

类比数组的合并,比较两个链表之前元素的大小,将其归纳到另一个链表。

目录

问题描述:

解决代码:

代码解析:

1.

2.

3.

4.

需要注意的是,当完成遍历之后,此时cur2有可能时NULL!

5.

需要注意的是

6.

ps:


解决代码:

以list2为主体,将list1合并到list2


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {struct ListNode* cur1 = list1;struct ListNode* cur2 = list2;struct ListNode* prev = NULL;   //不可以放在循环内部,否则会出现空指针问题while(cur1 && cur2){if(cur1->val <= cur2->val){if(cur2 == list2){list1 = cur1->next;cur1->next = cur2;cur2 = cur1;cur1 = list1;list2 = cur2;}else{list1 = cur1->next;cur1->next = cur2;prev->next = cur1;prev = cur1;cur1 = list1;}}else{prev = cur2;cur2 = cur2->next;}}//此时cur2已经是NULL,不能以用cur2//prev本身初始化时就是NULL!所以需要判断!  cur1若全部添加到cur2之后,那么cur1也是NULL,所以cur1也需要断言。//判断要写在解引用语句之前!如果已经去解引用了,那么判断将无意义!if(cur1 && prev && prev->val < cur1->val)  //如果list2遍历结束,都找出不大于cur1->val的值prev->next = cur1;if(list2)    //注意是否为空!return list2;elsereturn list1;  
}

代码解析:

1.

struct ListNode* cur1 = list1;

    struct ListNode* cur2 = list2;

    struct ListNode* prev = NULL;   //不可以放在循环内部,否则会出现空指针问题

既然要遍历整个链表,那就要建立cur指针,不断往下移动,从而完成遍历。

对于链表的链接,需要一个prev指针,将链表的上一个节点与下一个节点链接。

2.

        if(cur1->val <= cur2->val){

           

            if(cur2 == list2){

                list1 = cur1->next;

                cur1->next = cur2;

                cur2 = cur1;

                cur1 = list1;

                list2 = cur2;

            }

在小于等于的前提下,当cur2从list2开始的时候,此时需要给list2“换头”。即需要把head1的元素整合到list2头部,所以要 list2 = cur2;

3.

  else{

                list1 = cur1->next;

                cur1->next = cur2;

                prev->next = cur1;

                prev = cur1;

                cur1 = list1;

            }

当完成换头之后,此时只需要将list1中的节点连接到list2中。

4.

else{

            prev = cur2;

            cur2 = cur2->next;

        }

这段代码表示,当无法满足 if(cur1->val <= cur2->val)时,需要让cur2往下遍历,找到满足if语句的节点。

需要注意的是,当完成遍历之后,此时cur2有可能时NULL!

5.

if(cur1 && prev && prev->val < cur1->val)  //如果list2遍历结束,都找出不大于cur1->val的值

        prev->next = cur1;

我们的思路是让cur2不断往下遍历,但是若最后的节点的val仍然小于cur1的val,此时cur1并没有完成遍历,只需要让cur1剩下的元素,连接到cur2尾部即可。

需要注意的是

cur1 && prev 该判断语句必须要添加,并且需要写在if语句的前半部分!

//判断要写在解引用语句之前!  如果已经去解引用了,那么判断将无意义!

原因:①prev初始化时为NULL,所以要让prev进行判断

          ②需要判断cur1有没有走到最后的NULL指针。

          ③需要用prev->val 而不是 cur2->val,此时cur2已经跳出while循环,说明cur2已经是空指针!

6.

if(list2)    //注意是否为空!

        return list2;

    else

        return list1;  

}

最后,当list2本身为空的,则需要返回list1

ps:

通过刷leetcode可知,leetcode的题目往往会给出很抽象的数据范围,链表本身就可能是空链表!!!

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

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

相关文章

AJAX概念和axios使用、URL、请求方法和数据提交、HTTP协议、接口、form-serialize插件

AJAX概念和axios使用 AJAX概念 AJAX就是使用XMLHttpRequest对象与服务器通信&#xff0c;它可以使用JSON、XML、HTML和text文本等格式发送和接收数据&#xff0c;AJAX最吸引人的就是它的异步特性&#xff0c;也就是说它可以在不重新刷新页面的情况下与服务器通信&#xff0c;…

vulhub中GitLab 任意文件读取漏洞复现(CVE-2016-9086)

GitLab是一款Ruby开发的Git项目管理平台。在8.9版本后添加的“导出、导入项目”功能&#xff0c;因为没有处理好压缩包中的软连接&#xff0c;已登录用户可以利用这个功能读取服务器上的任意文件。 环境运行后&#xff0c;访问http://your-ip:8080即可查看GitLab主页&#xff0…

【鸿蒙HarmonyOS开发笔记】状态管理入门

状态管理 为了方便开发者管理组件状态&#xff0c;ArkTS 提供了一系列状态相关的装饰器&#xff0c;例如State&#xff0c;Prop&#xff0c;Link&#xff0c;Provide和Consume等等。 State State用于装饰当前组件的状态变量&#xff0c;State装饰的变量发生变化时会驱动当前组…

uniapp移动端 IOS系统下无法与webview通信

不知道有没有人遇到过这个问题 我的页面嵌套了一个webview&#xff08;文件位于项目的hybrif/html&#xff09;目录下 使用evalJS与webview进行通信 代码如下 在安卓里运行是没问题的&#xff0c;但在苹果手机上一直无法通信 连接真机&#xff0c;打印evalJS是个方法&#xf…

Blocks —— 《Objective-C高级编程 iOS与OS X多线程和内存管理》

目录 Blocks概要什么是BlocksOC转C方法关于几种变量的特点 Blocks模式Block语法Block类型 变量截获局部变量值__block说明符截获的局部变量 Blocks的实现Block的实质 Blocks概要 什么是Blocks Blocks是C语言的扩充功能&#xff0c;即带有局部变量的匿名函数。 顾名思义&#x…

email + celery+django 异步发送邮件功能的实现

主要流程&#xff1a; django通过发件服务器到收件服务器&#xff0c;最后到收件人 邮件配置设置需要打开SMTP/IMAP并获的授权码&#xff0c;完成授权功能实现发送给收件人 邮件配置请参考另一博客https://blog.csdn.net/qq_44238024/article/details/136277821 项目结构树…

【Linux杂货铺】进程的基本概念

目录 &#x1f308;前言&#x1f308; &#x1f4c1;进程的概念 &#x1f4c2;描述进程-PCB &#x1f4c2; 查看进程 &#x1f4c2; 查看正在运行的程序 &#x1f4c2;杀死进程 &#x1f4c2;通过系统调用获取进程标识符 &#x1f4c2;通过系统调用创建进程 &#x1f…

纯 CSS 实现文字换行环绕效果

实现效果 实现代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta name"viewport" content"widthdevice-width, initial-scale1.0" /><title>Document</title><…

蓝桥杯并查集|路径压缩|合并优化|按秩合并|合根植物(C++)

并查集 并查集是大量的树&#xff08;单个节点也算是树&#xff09;经过合并生成一系列家族森林的过程。 可以合并可以查询的集合的一种算法 可以查询哪个元素属于哪个集合 每个集合也就是每棵树都是由根节点确定&#xff0c;也可以理解为每个家族的族长就是根节点。 元素集合…

Transformer的前世今生 day02(神经网络语言模型

神经网络语言模型 使用神经网络的方法&#xff0c;去完成语言模型的两个问题&#xff0c;下图为两层感知机的神经网络语言模型&#xff1a; 以下为预备概念 感知机 线性模型可以用下图来表示&#xff1a;输入经过线性层得到输出 线性层 / 全连接层 / 稠密层&#xff1a;假…

Etcd 介绍与使用(入门篇)

etcd 介绍 etcd 简介 etc &#xff08;基于 Go 语言实现&#xff09;在 Linux 系统中是配置文件目录名&#xff1b;etcd 就是配置服务&#xff1b; etcd 诞生于 CoreOS 公司&#xff0c;最初用于解决集群管理系统中 os 升级时的分布式并发控制、配置文件的存储与分发等问题。基…

phpstudy搭建简单渗透测试环境upload-labs、DVWA、sqli-labs靶场

好久没有做渗透相关的试验了&#xff0c;今天打开phpstudy发现很多问题&#xff0c;好多环境都用不了&#xff0c;那就卸载重装吧&#xff0c;顺便记录一下。 小皮下载地址&#xff1a; https://www.xp.cn/download.html 下载安装完成 一、下载搭建upload-labs环境 github…

mysql与redis数据测试

题目要求 1.新建一张user表&#xff0c;在表内插入10000条数据。 2.①通过jdbc查询这10000条数据&#xff0c;记录查询时间。 ②通过redis查询这10000条数据&#xff0c;记录查询时间。 3.再次查询这一万条数据&#xff0c;要求根据年龄进行排序&#xff0c;mysql和redis各实现…

【GPT-SOVITS-03】SOVITS 模块-生成模型解析

说明&#xff1a;该系列文章从本人知乎账号迁入&#xff0c;主要原因是知乎图片附件过于模糊。 知乎专栏地址&#xff1a; 语音生成专栏 系列文章地址&#xff1a; 【GPT-SOVITS-01】源码梳理 【GPT-SOVITS-02】GPT模块解析 【GPT-SOVITS-03】SOVITS 模块-生成模型解析 【G…

vb.net+zxing.net随机彩色二维码、条形码

需要zxing库支持ZXing.NET Generate QR Code & Barcode in C# Alternatives | IronBarcode 效果图&#xff1a; 思路&#xff1a;先生成1个单位的二维码&#xff0c;然后再通过像素填充颜色&#xff0c;颜色数组要通过洗牌算法 洗牌算法 Dim shuffledCards As New List(…

Java八股文(MyBatis Plus)

Java八股文のMyBatis Plus MyBatis Plus MyBatis Plus MyBatis Plus 是什么&#xff1f;它与 MyBatis 有什么区别&#xff1f; MyBatis Plus 是基于 MyBatis 进行扩展的一款持久层框架&#xff0c;它提供了一系列增强功能&#xff0c;简化了 MyBatis 的使用。 与 MyBatis 相比…

K8S POD 启动探针 startupProbe 的使用

当我们启动一个POD 时&#xff0c; 当k8s detect 里面的容器启动成功时&#xff0c; 就会认为这个POD 启动完成了&#xff0c; 通常就会在状态里表示 ready 1/1 … 例如 rootk8s-master:~# kubectl get pods NAME READY STATUS RESTARTS AGE bq-api-demo 1…

有来团队后台项目-解析7

sass 安装 因为在使用vite 创建项目的时候&#xff0c;已经安装了sass&#xff0c;所以不需要安装。 如果要安装&#xff0c;那么就执行 npm i -D sass 创建文件 src 目录下创建文件 目录结构如图所示&#xff1a; reset.scss *, ::before, ::after {box-sizing: border-…

矩阵中移动的最大次数

文章目录 所属专栏:BFS算法 题目链接 思路如下&#xff1a; 1.首先我们需要从第一列开始遍历&#xff0c;寻找每一个都能够满足条件的位置&#xff0c;将它插入到数组里面 2.第一列遍历完了后我们先判断第一列的数是否都满足条件插入到数组里面&#xff0c;如果数组为空&#…

电脑充电器能充手机吗?如何给手机充电?

电脑充电器可以给手机充电吗&#xff1f; 电脑充电器可以给手机充电&#xff0c;但前提是电脑充电器的功率输出与手机的功率匹配且接口匹配。 假设电脑充电器的输出功率为5V/2A&#xff0c;手机也支持5V/2A的输入功率。 只要接口匹配&#xff0c;就可以使用电脑充电器给手机充…