[LeetCode]-138. 随机链表的复制

目录

 题目

解题步骤

1.拷贝节点插入原节点的后面

2.置每个拷贝节点random

3.拷贝节点解下来,尾插到一起,恢复原链表

完整代码


 题目

给你一个长度为 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 作为传入参数。

示例:

解题步骤

1.拷贝节点插入原节点的后面

给原链表的每个节点都拷贝一份,其中每个新节点的值都设为其对应的原节点的值,将新节点都分别插入到原节点的后面,组成了一个新链表。

如下图:

 代码

struct Node* copyRandomList(struct Node* head) {struct Node* cur=head;while(cur){//拷贝节点struct Node* next=cur->next;struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;//插入cur->next=copy;copy->next=next;//往后走cur=next;}

2.置每个拷贝节点random

由于新链表节点上的random指向状态要和原链表节点上的相同,因此原节点后面的拷贝出来的节点的random指向的节点应该是原节点random指向节点的后面拷贝节点,置每个拷贝节点random可以用copy->random=cur->random->next,(原节点random置空时除外,此时拷贝节点random也置空)。

如下图:

代码

cur=head;
while(cur)
{struct Node* copy=cur->next;//置copy->randomif(cur->random==NULL)copy->random=NULL;elsecopy->random=cur->random->next;cur=copy->next;
}

3.拷贝节点解下来,尾插到一起,恢复原链表

接下来就是单链表的节点的删除和尾插的内容了,先创建一个拷贝拷贝链表的头copyhead,创建copytail用于保存解下的拷贝节点,创建copy用来遍历解开拷贝的节点,创建单链表删除节点时需要的两边节点cur、next,随着拷贝节点向后遍历,cur和next一起到null时结束遍历。

如下图:

代码

cur=head;
struct Node* copyhead=NULL,*copytail=NULL;
while(cur)
{struct Node* copy=cur->next;struct Node* next=copy->next;//copy节点尾插到新链表if(copytail==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}//恢复原链表cur->next=next;cur=next;
}
return copyhead;}

完整代码

struct Node* copyRandomList(struct Node* head) {struct Node* cur=head;while(cur){//拷贝节点struct Node* next=cur->next;struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;//插入cur->next=copy;copy->next=next;//往后走cur=next;}
//cur=head;
while(cur)
{struct Node* copy=cur->next;//置copy->randomif(cur->random==NULL)copy->random=NULL;elsecopy->random=cur->random->next;cur=copy->next;
}cur=head;
struct Node* copyhead=NULL,*copytail=NULL;
while(cur)
{struct Node* copy=cur->next;struct Node* next=copy->next;//copy节点尾插到新链表if(copytail==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}//恢复原链表cur->next=next;cur=next;
}
return copyhead;}

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

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

相关文章

异常断电文件损坏docker服务异常处理

问题场景 我们在某地部署信控平台,当初是在产品研发早期,采取的还是Windows服务器部署虚拟机的方式使用virtualbox导入centos7虚拟机,虚拟机里运行docker服务,使用docker-compose统一管理客户今天上午反馈,昨天断电了…

图文详解 VCF 生信格式 (变异信息)

文章目录 一、vcf 格式介绍二、vcf 资源文件三、vcf 文件详解3.1 主要字段3.2 INFO 中的常见信息3.3 FORMAT 和 SAMPLEs 中的信息 四、vcf 的记录模式4.1 只记录变异本身的信息4.2 记录个体或个体组织的变异信息4.3 记录群体或家系的变异信息 五、记录标准5.1 记录多核苷酸多样…

策略模式(Stragedy)

简介 策略模式将策略(方法)与实体类相分离,使用聚合/组合替代继承。 思想:少用耦合性高的继承,尽量用聚合/组合来代替。 优点:将策略独立于实体类,策略的实现更加灵活,易于理解扩展…

辐射骚扰整改思路及方法:方案合并与原理探究 ?|深圳比创达电子EMC

一、方案合并 将EMI滤波器(选择了231,是因为额定直流电流相比421更大)和RC电路(10Ω2200pF)合并到产品上,再行测试,堪称完美!至此,辐射整改完成。 图1 最终测试结果 231…

【链接装载与库】动态链接(下)

动态链接 》上篇《 延迟绑定 (PLT) 动态链接的确有很多优势,比静态链接要灵活得多,但它是以牺牲一部分性能为代价的。主要原因是动态链接下对于全局和静态的数据访问都要进行复杂的GOT定位,然后间接寻址;对于模块间的调用也要先…

Python高级语法----深入理解Python协程

文章目录 什么是协程?Python中的协程基本示例协程和事件循环总结Python协程是一种非常强大的并发编程概念,让你能够高效地处理多任务。协程在Python中的使用已经变得越来越流行,特别是在异步编程中。本文将用通俗易懂的语言来介绍协程的概念,并提供实际的代码示例和执行结果…

javascript 操作mysql数据库

目录 一:Javascript访问MYSQL 二:JavaScript中操作Mysql数据库实例 一:Javascript访问MYSQL 1、下载MYSQL的ODBC连接 2、在JS中建立ODBC连接如下: var con new ActiveXObject("ADODB.Connection"); con.Connection…

JS加密/解密之你是否真的明白xss

摘要:跨站脚本攻击(XSS)是当前Web应用程序中最常见的安全威胁之一。本文通过综合分析XSS攻击的原理和特点,提出了一系列全面的防御策略,包括输入验证和过滤、输出编码以及Content Security Policy(CSP&…

护眼灯买哪种好,五款热门专业护眼台灯推荐

护眼台灯的光照一般比较均匀,相比普通台灯,一般具有防蓝光、防频闪等功能,能够提供一个健康舒适的学习、生活灯光环境,建议选购内置智能感光模式的护眼台灯,以确保灯光亮度一直处于均衡状态,让眼睛更轻松。…

查看apk签名

cmd 命令: keytool -v -list -keystore "E:\xxx\release.jks"

浅谈蒙牛乳业有限公司变压器配电系统改造项目的应用

Application of power management system in transformer distribution system Renovation project of Inner Mongolia Meng Niu Dairy (Group) Co., Ltd. 摘要:本文介绍蒙牛乳业(当阳)有限公司低压系统改造电力监控系统,采用智能…

尚硅谷大数据项目《在线教育之实时数仓》笔记006

视频地址:尚硅谷大数据项目《在线教育之实时数仓》_哔哩哔哩_bilibili 目录 第9章 数仓开发之DWD层 P041 P042 P043 P044 P045 P046 P047 P048 P049 P050 P051 P052 第9章 数仓开发之DWD层 P041 9.3 流量域用户跳出事务事实表 P042 DwdTrafficUserJum…

11.9树的表示方法(孩子,父亲,孩子兄弟),树、森林的遍历,一些操作,决策树,前缀树

父亲表示法 优缺点:利用了树中除根结点外每个结点都有唯一的父节点这个性质,很容易找到树根,但是找孩子需要遍历整个线性表。 最近公共祖先 第一种方法,找路径然后比较 如果是搜索树,可以二分查找 不是,…

计算机网络期末复习-Part1

1、列举几种接入网技术:ADSL,HFC,FTTH,LAN,WLAN ADSL(Asymmetric Digital Subscriber Line):非对称数字用户线路。ADSL 是一种用于通过电话线连接到互联网的技术,它提供…

RabbitMQ集群

RabbitMQ概述 1.RabbiMQ简介 RabbiMQ是⽤Erang开发的,集群⾮常⽅便,因为Erlang天⽣就是⼀⻔分布式语⾔,但其本身并不⽀持负载均衡。支持高并发,支持可扩展。支持AJAX,持久化,用于在分布式系统中存储转发消…

excel中超级表和普通表的相互转换

1、普通表转换为超级表 选中表内任一单元格,然后按CtrlT,确认即可。 2、超级表转换为普通表 选中超级表内任一单元格,右键,表格,转换为区域,确定即可。 这时虽然已经变成了普通表,但样式没有…

vue3怎么获取el-form的元素节点

在元素中使用ref设置名称 在ts中通过从element-plus引入formInstance,设置formRef同名名称字段来获取el-form节点

flutter笔记:骨架化加载器

flutter笔记 骨架化加载器 - 文章信息 - Author: Jack Lee (jcLee95) Visit me at: https://jclee95.blog.csdn.netEmail: 291148484163.com. Shenzhen ChinaAddress of this article:https://blog.csdn.net/qq_28550263/article/details/134224135 【介绍】:本文介…

OpenCV 输出文本

PutText() 输出文本 OpenCV5 将支持中文字符的输出, 当前版本OpenCV4原生不支持, 可以使用Contrib包FreeType方式实现, 不过比较麻烦.为了省事, 也可以通过将Mat转成bitmap,然后使用GDI方式输出中文字符. 示例代码 /// <summary>/// OpenCV暂时不能支持中文字符输出,显示…