力扣138:随机链表的复制
力扣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 作为传入参数。
示例 1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2:

输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]
示例 3:

输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]
提示:
0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。
分析:
这道题的意思是对一个 含有随机指针的单链表进行复制,也就是说,复制之后也是一个完全一样的含有随机指针的单链表。原来单链表中每个节点的随机指针指向的节点,在复制之后,依然 也得是一样的。
对于这道题,三步走:
- 第一步 拷贝节点在原节点后面:
将原链表中每个节点依次拷贝一份,并插入到对应节点后面。在遍历原链表时,cur用于记录原链表中当前节点。动态开辟一个copy节点,用于存储拷贝的节点。
在插入时,先执行copy->next=cur->next;再执行cur->next=copy。

完成依次拷贝并插入到对应节点后,将cur后移。这里的后移是在原链表上后移动,但是原链表的第一个节点在后面插了一个节点,因此cur一个需要移动两个节点,即cur=cur->next->next或者cur=copy->next。

什么时候遍历结束呢?
当前指针cur为空时,表示原来的链表遍历结束。

- 第二步:处理拷贝节点copy的random
原来链表的每个节点都有一个随机指针,因此在复制的时候,也要将随机指针赋值到拷贝的链表中。
以下面这个情况为例:

可以看到,第一个节点7的随机指针指向的是NULL,第二个节点13的随机指针指向的是第一个节点7,第三个节点11的随机指针指向的是第五个节点1…
当原链表节点的随机指针指向NULL时,那么我们对应的拷贝节点的随机指针也指向NULL,即copy->random=NULL

当原链表节点的随机指针指向另外一个节点时,可以使对应的拷贝节点copy指向当前节点cur随机节点指向的节点的下一个节点,即copy->random=cur->random->next,这一步是整个代码的灵魂,这里可能有点绕,结合下图去分析:

当前指针cur为空时,遍历结束。
- 第三步:拷贝节点copy解下来尾插:
这一步,主要使用是单链表中尾插操作。
需要先创建一个新的头指针和尾指针,当尾指针为空时,也就是说新链表里面还没有节点时,此时插入的节点就是这个新链表的头节点
遍历链表,当前指针cur为空时,遍历结束
拷贝指针copy所指向的节点,需要尾插到新链表里面,copy指针即copy=cur->next,实现尾插:tail->next=copy
将拷贝节点解下来后,还需要将原链表复原,因此,需要创建一个next指针指向copy->next,next也就是原链表的下一个节点。补原链表,cur->next=next
cur移动到next位置,继续执行上述操作,直到cur为空
最后只需要返回新链表的头节点,即拷贝后的链表。
代码:
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/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=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;}struct Node* newhead=NULL,*tail=NULL;cur=head;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;
}
相关文章:
力扣138:随机链表的复制
力扣138:随机链表的复制 题目描述: 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成ÿ…...
C语言左移与右移学习
在学习左移与右移之前,我们首先要学习两种移位运算:逻辑移位和算数移位。 逻辑位移:移出去的位丢弃,空缺位用0补充。 算数位移:移出去的位丢弃,空缺位用符号位补充。 左移 左移是高位溢出,低…...
asp.net core mvc之 视图
一、在控制器中找到匹配视图,然后渲染成 HTML 代码返回给用户 public class HomeController : Controller {public IActionResult Index(){return View(); //默认找 Views/Home/Index.cshtml ,呈现给用户} } 二、指定视图 1、控制器 publ…...
ChatGLM3 tool_registry.py 代码解析
ChatGLM3 tool_registry.py 代码解析 0. 背景1. tool_registry.py 0. 背景 学习 ChatGLM3 的项目内容,过程中使用 AI 代码工具,对代码进行解释,帮助自己快速理解代码。这篇文章记录 ChatGLM3 tool_registry.py 的代码解析内容。 1. tool_re…...
js实现定时刷新,并设置定时器上限
定时器 在js中,有两种定时器: 倒计时定时器 倒计时定时器,也叫延时定时器或一次性定时器 功能:倒计时多长时间后执行某个动作 语法:setTimeout(function, timeout); 返回值:int类型,当前定时器…...
常用Linux命令
df -h #查看磁盘 kill -9 pid #强制关闭程序 ifconfig #查看网卡信息 last …...
【C++】获取指定点所在屏幕的尺寸
问题 多个显示器时,获取指定点所在的显示器的尺寸。 分析 之前整理过获取屏幕尺寸的方法:https://blog.csdn.net/m0_43605481/article/details/125024500多显示器时,需要用到GetSystemMetrics、EnumDisplayDevices、EnumDisplaySettings函…...
软文发布如何选择对应的媒体
企业做软文推广第一步,就是选择合适的媒体进行投放,然而许多企业不知道如何选择合适的媒体导致推广工作十分被动,无法取得效果,今天媒介盒子就来和大家分享,企业应该如何选择对应的媒体。 一、 媒体类型 根据软文类型…...
Django如何创建表关系,Django的请求声明周期流程图
【1】表与表之间的关系 一对一 左表的一条记录对应右表的一条记录,反之亦然 多对一 左表的一条记录对应右表的多条记录,反之不成立 多对多 左表的一条记录对应右表的多表记录,反之成立 【2】django中创建表关系 class Book(models.Model):t…...
微服务-我对Spring Clound的理解
官网:https://spring.io/projects/spring-cloud 官方说法:Spring Cloud 为开发人员提供了快速构建分布式系统中一些常见模式的工具(例如配置管理、服务发现、熔断器、智能路由、微代理、控制总线、一次性令牌、全局锁、领导选举、分布式会话…...
安防监控EasyCVR视频汇聚平台无法接入Ehome5.0是什么原因?该如何解决?
视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同,支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。安防平台EasyCVR拓展性强,视频能力丰富,具体可实现视频监控直播、视频轮播、视频录像、云存储、回放…...
机器学习——逻辑回归
目录 一、分类问题 监督学习的最主要类型 二分类 多分类 二、Sigmoid函数 三、逻辑回归求解 代价函数推导过程(极大似然估计): 交叉熵损失函数 逻辑回归的代价函数 代价函数最小化——梯度下降: 编辑 正则化 四、逻辑…...
自动驾驶学习笔记(七)——感知融合
#Apollo开发者# 学习课程的传送门如下,当您也准备学习自动驾驶时,可以和我一同前往: 《自动驾驶新人之旅》免费课程—> 传送门 《Apollo Beta宣讲和线下沙龙》免费报名—>传送门 文章目录 前言 感知融合 卡尔曼滤波 融合策略 实…...
【Java0基础学Java第八颗】 -- 继承与多态 -- 多态
8.继承与多态 8.2 多态8.2.1 多态的概念8.2.2 多态实现条件8.2.3 重写8.2.4 向上转型和向下转型8.2.5 向下转型8.2.6 多态的优缺点8.2.7 避免在构造方法中调用重写的方法 8.2 多态 8.2.1 多态的概念 通俗来说就是多种形态,具体点就是去完成某个行为,当…...
玩转ansible之参数调试和文件操作篇
更多IT技术文章,欢迎关注微信公众号“运维之美” 玩转ansible之参数调试和文件操作篇 01 剧本调试和帮助02 使用场景举例 上节我们学习了使用ansible进行软件安装,那么安装完软件后,就需要linux系统和软件配置修改了,对于linux主机…...
JVM虚拟机:垃圾回收器之Parallel Old(老年代)
本文重点 本文将学习老年代的另外一种垃圾回收器Parallel Old(PO),这是一种用于老年代的并行化垃圾回收器,它使用标记整理算法进行垃圾回收。 历史 在1.6之前,新生代使用Parallel Scavenge只能搭配老年代的Serial Old收集器,而…...
Stream流的groupingBy
Stream流的groupingBy 简单使用 业务场景:现在有100个人,这些人都年龄分部在18-30岁之间。现要求把他们按照年龄进行分组 key:年龄 value:数据列表 public void listToMapGroup() {//这里假设通过listStreamService.list();方法…...
如何在不结束tcpdump的情况下复制完整的pcap
tcpdump正在运行的时候,他写入的pcap可能是不完整的,通常我们要结束掉tcpdump才能拿到完整的pcap,否则wireshark打开的时候会提示:The capture file appears to have been cut short in the middle of a packet。这可能是因为tcpd…...
maven POM文件总体配置说明
<project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation"http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd "> <!-- 父项目的坐…...
49.批处理命令(1/2)
目录 一批处理。 (1)批处理定义。 (2)常见命令。 (2.1)rem和:: (2.2)echo和。 (2.3)pause。 (2.4)errorlevel。 (…...
智能代码生成质量保障(2024年Gartner验证的TOP3工业级检测工具链深度拆解)
第一章:智能代码生成代码质量保障 2026奇点智能技术大会(https://ml-summit.org) 智能代码生成正从辅助编程工具演进为软件交付链路中可信赖的质量守门人。其质量保障能力不再仅依赖模型输出的语法正确性,而需贯穿语义一致性、安全合规性、可维护性与运…...
AI辅助排版:设计领域的应用方法与落地实践
数字化内容生产节奏不断加快,品牌方对内容输出的频率和质量要求同步提升。不少中小设计团队因为排版效率不足,无法承接高频次的内容输出需求。特别是电商大促节点,不少中小团队一周要承接近百套商品详情页、平台活动海报、新媒体种草内容的排…...
2026奇点智能技术大会核心成果发布(AI文档生成引擎v3.2正式开源)
第一章:2026奇点智能技术大会:AI接口文档生成 2026奇点智能技术大会(https://ml-summit.org) 在2026奇点智能技术大会上,AI驱动的接口文档自动生成技术成为核心议题之一。该技术依托多模态大模型对源码、注释、测试用例及通信日志的联合理解…...
Kali Linux实战:用SET工具包5分钟克隆一个钓鱼网站(附谷歌浏览器登录凭证捕获演示)
Kali Linux实战:5分钟构建钓鱼网站与凭证捕获全流程 在网络安全领域,渗透测试工具的应用能力直接决定了安全防护的有效性。Social Engineer Toolkit(SET)作为Kali Linux中的明星工具包,以其高度集成化和易用性著称&am…...
从理论到实践:用PROTUES快速验证差分放大电路的计算公式
从理论到实践:用PROTUES快速验证差分放大电路的计算公式 在电子工程领域,差分放大电路的设计与验证是一个绕不开的经典课题。作为模拟电路设计的基石,它完美诠释了"抑制共模干扰,放大差模信号"这一核心理念。然而&#…...
如何通过游戏化编程轻松掌握Python与JavaScript:CodeCombat终极指南
如何通过游戏化编程轻松掌握Python与JavaScript:CodeCombat终极指南 【免费下载链接】codecombat Game for learning how to code. 项目地址: https://gitcode.com/gh_mirrors/co/codecombat 想要让编程学习变得像玩游戏一样有趣吗?CodeCombat正是…...
基于图神经网络的智能合约漏洞检测
研一小白,我的课题就是基于图神经网络做合约漏洞检测,有无高手指教一下啊,不知道怎么办,所以来csdn上碰碰运气,看有没有做过类似课题的,关于数据集怎么找、怎么标记以及如何写小论文等...
Qwen2.5-VL 算法解析
Qwen2.5-VL 本质上是一个 Qwen2.5 LLM 原生动态分辨率 ViT 视觉到语言的 MLP 压缩器 面向图像/视频的时间对齐版 MRoPE 的统一多模态自回归模型。它相对 Qwen2-VL 的核心升级,不是简单“换了个更大的底座”,而是把 视觉编码效率、长视频时间建模、文档…...
STM32F429 HAL库 DMA方式实现SD卡高效存储.csv数据
1. 为什么需要DMA方式存储.csv数据 当你用STM32F429做数据采集时,最头疼的就是CPU被数据传输占满的问题。我去年做工业传感器项目时就遇到过——采集10个通道的模拟量数据,还要实时计算和存储,结果发现光是往SD卡写数据就吃掉了70%的CPU资源。…...
Three.js小程序适配版终极指南:快速打造微信小程序3D交互体验
Three.js小程序适配版终极指南:快速打造微信小程序3D交互体验 【免费下载链接】threejs-miniprogram WeChat MiniProgram adapted version of Three.js 项目地址: https://gitcode.com/gh_mirrors/th/threejs-miniprogram 想在微信小程序中轻松实现炫酷的3D效…...
