数据结构链表力扣例题AC(4)——代码以及思路记录

21. 合并两个有序链表

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

AC

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}struct ListNode* head = NULL;struct ListNode* 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;
}

代码思路

最简单的方法就是比较两个链表中的值,将小的尾插到新链表中。

创建一个新链表,一个指针head指向头结点,一个指针tail进行尾插操作,然后开始进行比较,结束条件是其中一方的值为空,如果tail还是NULL,说明新链表还没有值,就将head和tail都指向小的那一个,如果tail不为空了,那么继续尾插,让他的next去存这个小的的地址,然后让tail前移。小的值所在的list也前移。当其中一个已经结束后,还不为空的那一个链表后面的所有节点都尾插到新链表即可,最后返回头结点地址head。

不建议使用将一个链表的值直接插入另一个链表的方法,写起来非常复杂。

138. 随机链表的复制(中等)

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

AC

struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;cur->next = copy;//cur = copy->next;  //两者相等cur = cur->next->next;}cur = head;while(cur){struct Node* copy = cur->next;if(cur->random == NULL) // 特殊情况处理{copy->random = NULL;}else{copy->random = cur->random->next; // 关键}cur = cur->next->next;}cur = head;struct Node* newhead = NULL,*tail = NULL;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;if(tail == NULL){newhead = tail = copy;}else{tail->next = copy;tail = tail->next;}cur->next = next;cur = next;}return newhead;
}

代码思路

这道题思路比较难想,且实现起来也较为复杂。

先解读题目,要做一个深拷贝,完成链表的复制并不复杂,但是此链表中不止存着next节点,还存着random随机节点,也就是说,每一个节点还存在一个random数值,存放着某一个节点的地址,这个地址是随机的,此处的随机可以是整条链表的任一个节点,可以是空指针,可以是下一个或上一个节点,甚至可以是自己,如图:

这道题的方法很难想到,这里直接讲解,在每一个节点后都创建一个copy节点,复制改节点,所有的copy节点就是新链表的组成部分,如图:

这样做的理由是什么呢,请看下一张图,这张图展现了random的关系:

这里看copy13,以他为例,copy13random按照原链表的random来讲应该指向节点值为7的节点,也就是图中的蓝色线条,指向copy7,那这样如何找到呢。使用cur记录原链表的13,使用copy记录新链表的13,那么copy13random,通过cur13random找到了cur7,此刻cur7copy7是链接起来的,那么他的next就是copy7,因此有等式 copy->random = cur->random->next

找到新链表的random后,移动cur指针和copy指针就可以将整条由原链表和新链表组成的链表的节点都实现复制,接着就将原链表和新链表拆分最后返回新链表的地址就可以了,具体的代码讲解在此不做赘述,只写关键思路,可根据上文中的代码自己分析。

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

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

相关文章

alibabacloud学习笔记06(小滴课堂)

讲Sentinel流量控制详细操作 基于并发线程进行限流配置实操 在浏览器打开快速刷新会报错 基于并发线程进行限流配置实操 讲解 微服务高可用利器Sentinel熔断降级规则 讲解服务调用常见的熔断状态和恢复 讲解服务调用熔断例子 我们写一个带异常的接口&#xff1a;

正交匹配追踪(Orthogonal Matching Pursuit, OMP)的MATLAB实现

压缩感知&#xff08;Compressed Sensing, CS&#xff09;是一种利用稀疏信号的先验知识&#xff0c;用远少于奈奎斯特采样定理要求的样本数目恢复整个信号的技术。正交匹配追踪&#xff08;Orthogonal Matching Pursuit, OMP&#xff09;是一种常见的贪婪算法&#xff08;Gree…

OCPP 1.6 接入实现文档

一、简介 OCPP&#xff08;Open Charge Point Protocol&#xff09;是一个开放的通信协议&#xff0c;用于充电站&#xff08;Charge Point&#xff09;与中央系统&#xff08;Central System&#xff0c;如充电站管理系统或服务提供商平台&#xff09;之间的通讯。本篇文档将…

谷歌搜索引擎关键词优化,竞价排名怎么做?大舍传媒

公司 大舍传媒成立于2005年&#xff0c;并从那时开始专注于谷歌搜索引擎优化&#xff08;SEO&#xff09;。如今&#xff0c;我们已经拥有了十八年的海外数字营销经验。我们为全球数千个国际知名品牌客户提供服务&#xff0c;是一家专注于技术的公司。 谷歌排名成果 在谷歌&…

Windows系统中定时执行python脚本

背景&#xff1a;本地Windows系统指定目录下会有文件的修改新增&#xff0c;这些变化的文件需要定时的被上传到git仓库中&#xff0c;这样不需要每次变更手动上传了。 首先编写一个检测文件夹下文件变化并且上传git仓库的python脚本(确保你已经在E:\edc_workspace\data_edc_et…

10.vue学习笔记(组件数据传递-props回调函数子传父+透传Attributes+插槽slot)

文章目录 1.组件数据传递2.透传Attributes&#xff08;了解&#xff09;禁用Attributes继承 3.插槽slot 1.组件数据传递 我们之前讲解过了组件之间的数据传递&#xff0c;props 和 自定义事件 两种方式 props&#xff1a;父传子 自定义事件&#xff1a;子传父 props通过额外方…

dell戴尔电脑灵越系列Inspiron 15 3520原厂Win11系统中文版/英文版

Dell戴尔笔记本灵越3520原装出厂Windows11系统包&#xff0c;恢复出厂开箱预装OEM系统 链接&#xff1a;https://pan.baidu.com/s/1mMOAnvXz5NCDO_KImHR5gQ?pwd3nvw 提取码&#xff1a;3nvw 原厂系统自带所有驱动、出厂主题壁纸、系统属性联机支持标志、Office办公软件、MyD…

2024.2.22 C++QT 作业

思维导图 练习题 1>完善对话框&#xff0c;点击登录对话框&#xff0c;如果账号和密码匹配&#xff0c;则弹出信息对话框&#xff0c;给出提示”登录成功“&#xff0c;提供一个Ok按钮&#xff0c;用户点击Ok后&#xff0c;关闭登录界面&#xff0c;跳转到其他界面。如果账…

Redis 工具类 与 Redis 布隆过滤器

Redis 工具类 1. 核心依赖 <!--redis--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId> </dependency> <dependency><groupId>com.google.guava…

leetcode(算法) 83.删除排序链表中的重复元素(python版)

需求 给定一个已排序的链表的头 head &#xff0c; 删除所有重复的元素&#xff0c;使每个元素只出现一次 。返回 已排序的链表 。 示例 1&#xff1a; 输入&#xff1a;head [1,1,2] 输出&#xff1a;[1,2] 示例 2&#xff1a; 输入&#xff1a;head [1,1,2,3,3] 输出&…

【Unity3D】ASE制作天空盒

找到官方shader并分析 下载对应资源包找到\DefaultResourcesExtra\Skybox-Cubed.shader找到\CGIncludes\UnityCG.cginc观察变量, 观察tag, 观察代码 需要注意的内容 ASE要处理的内容 核心修改 添加一个Custom Expression节点 code内容为: return DecodeHDR(In0, In1);outp…

jenkins报错:Pseudo-terminal will not be allocated because stdin is not a terminal

jenkins的流水线部分代码如下 sh ssh root192.168.2.234 << remotessh cd /var/lib/jenkins/workspace/txkc /usr/local/maven/apache-maven-3.8.6/bin/mvn clean package -U ls remotessh执行流水线出现报错&#xff1a;Pseudo-terminal will not be allocated because…

【数据结构】排序(1)

目录 一、概念&#xff1a; 二、直接插入排序&#xff1a; 三、希尔排序&#xff1a; 四、直接选择排序&#xff1a; 五、堆排序&#xff1a; 六、冒泡排序&#xff1a; 一、概念&#xff1a; 排序的概念&#xff1a; 使一串记录&#xff0c;按照其中的某个或某些关键字…

【Crypto | CTF】BUUCTF RSA2

天命&#xff1a;密码学越来越难了&#xff0c;看别人笔记都不知道写啥 天命&#xff1a;莫慌&#xff0c;虽然我不会推演法&#xff0c;但我可以用归纳法 虽然我不知道解题的推演&#xff0c;但我可以背公式啊哈哈哈 虽然我不会这题&#xff0c;但是我也能做出来 公式我不知…

百度百科词条在网络推广中的六大作用

也许很多网友都发现了&#xff0c;在网上查资料&#xff0c;百科词条往往是优先展示的。一方面因为百科是搜索引擎自身的平台&#xff0c;另一方面就是因为百科信息权威&#xff0c;网友认可度高。所以企业开展网络营销&#xff0c;百科营销是一块重要阵地。 也有的企业认为百科…

代码检测规范和git提交规范

摘要&#xff1a;之前开发的项目&#xff0c;代码检测和提交规范都是已经配置好的&#xff0c;最近自己新建的项目就记录下相关配置过程。 1. ESlint配置 2013年6月创建开源项目&#xff0c;提供一个插件化的JavaScript代码检测工具&#xff0c;创建项目是生成的eslintrc.js文…

Elasticsearch从入门到精通-01认识Elasticsearch

Elasticsearch从入门到精通-01认识Elasticsearch &#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是程序员行走的鱼 &#x1f342;博主从本篇正式开始ES学习&#xff0c;希望小伙伴可以一起探讨 &#x1f4d6; 本篇主要介绍和大家一块简单认识下ES并了解ES中的主要角色…

装饰模式(Decorator Pattern)

定义 装饰模式&#xff08;Decorator Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许通过将对象包装在装饰器类的实例中来动态地添加新的行为和责任。这种模式可以在不修改现有代码的情况下&#xff0c;灵活地扩展对象的功能。 示例 考虑一个咖啡店的场景&…

springboot集成mqtt

文章目录 前言一、MQTT是什么&#xff1f;二、继承步骤1.安装MQTT2.创建项目&#xff0c;引入依赖3. 对应步骤2的代码3 测试 总结mqtt 启动后访问地址 前言 随着物联网的火热,MQTT的应用逐渐增多 曾经也有幸使用过mqtt,今天正好总结下MQTT的使用; 一、MQTT是什么&#xff1f;…

[OpenAI]继ChatGPT后发布的Sora模型原理与体验通道

前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家&#xff1a;https://www.captainbed.cn/z ChatGPT体验地址 文章目录 前言OpenAI体验通道Spacetime Latent Patches 潜变量时空碎片, 建构视觉语言系统…