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

力扣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&#xff1a;随机链表的复制 题目描述&#xff1a; 给你一个长度为 n 的链表&#xff0c;每个节点包含一个额外增加的随机指针 random &#xff0c;该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成&#xff…...

C语言左移与右移学习

在学习左移与右移之前&#xff0c;我们首先要学习两种移位运算&#xff1a;逻辑移位和算数移位。 逻辑位移&#xff1a;移出去的位丢弃&#xff0c;空缺位用0补充。 算数位移&#xff1a;移出去的位丢弃&#xff0c;空缺位用符号位补充。 左移 左移是高位溢出&#xff0c;低…...

asp.net core mvc之 视图

一、在控制器中找到匹配视图&#xff0c;然后渲染成 HTML 代码返回给用户 public class HomeController : Controller {public IActionResult Index(){return View(); //默认找 Views/Home/Index.cshtml &#xff0c;呈现给用户} &#xff5d; 二、指定视图 1、控制器 publ…...

ChatGLM3 tool_registry.py 代码解析

ChatGLM3 tool_registry.py 代码解析 0. 背景1. tool_registry.py 0. 背景 学习 ChatGLM3 的项目内容&#xff0c;过程中使用 AI 代码工具&#xff0c;对代码进行解释&#xff0c;帮助自己快速理解代码。这篇文章记录 ChatGLM3 tool_registry.py 的代码解析内容。 1. tool_re…...

js实现定时刷新,并设置定时器上限

定时器 在js中&#xff0c;有两种定时器&#xff1a; 倒计时定时器 倒计时定时器&#xff0c;也叫延时定时器或一次性定时器 功能&#xff1a;倒计时多长时间后执行某个动作 语法&#xff1a;setTimeout(function, timeout); 返回值&#xff1a;int类型&#xff0c;当前定时器…...

常用Linux命令

df -h #查看磁盘 kill -9 pid #强制关闭程序 ifconfig #查看网卡信息 last …...

【C++】获取指定点所在屏幕的尺寸

问题 多个显示器时&#xff0c;获取指定点所在的显示器的尺寸。 分析 之前整理过获取屏幕尺寸的方法&#xff1a;https://blog.csdn.net/m0_43605481/article/details/125024500多显示器时&#xff0c;需要用到GetSystemMetrics、EnumDisplayDevices、EnumDisplaySettings函…...

软文发布如何选择对应的媒体

企业做软文推广第一步&#xff0c;就是选择合适的媒体进行投放&#xff0c;然而许多企业不知道如何选择合适的媒体导致推广工作十分被动&#xff0c;无法取得效果&#xff0c;今天媒介盒子就来和大家分享&#xff0c;企业应该如何选择对应的媒体。 一、 媒体类型 根据软文类型…...

Django如何创建表关系,Django的请求声明周期流程图

【1】表与表之间的关系 一对一 左表的一条记录对应右表的一条记录&#xff0c;反之亦然 多对一 左表的一条记录对应右表的多条记录&#xff0c;反之不成立 多对多 左表的一条记录对应右表的多表记录&#xff0c;反之成立 【2】django中创建表关系 class Book(models.Model):t…...

微服务-我对Spring Clound的理解

官网&#xff1a;https://spring.io/projects/spring-cloud 官方说法&#xff1a;Spring Cloud 为开发人员提供了快速构建分布式系统中一些常见模式的工具&#xff08;例如配置管理、服务发现、熔断器、智能路由、微代理、控制总线、一次性令牌、全局锁、领导选举、分布式会话…...

安防监控EasyCVR视频汇聚平台无法接入Ehome5.0是什么原因?该如何解决?

视频云存储/安防监控EasyCVR视频汇聚平台基于云边端智能协同&#xff0c;支持海量视频的轻量化接入与汇聚、转码与处理、全网智能分发、视频集中存储等。安防平台EasyCVR拓展性强&#xff0c;视频能力丰富&#xff0c;具体可实现视频监控直播、视频轮播、视频录像、云存储、回放…...

机器学习——逻辑回归

目录 一、分类问题 监督学习的最主要类型 二分类 多分类 二、Sigmoid函数 三、逻辑回归求解 代价函数推导过程&#xff08;极大似然估计&#xff09;&#xff1a; 交叉熵损失函数 逻辑回归的代价函数 代价函数最小化——梯度下降&#xff1a; ​编辑 正则化 四、逻辑…...

自动驾驶学习笔记(七)——感知融合

#Apollo开发者# 学习课程的传送门如下&#xff0c;当您也准备学习自动驾驶时&#xff0c;可以和我一同前往&#xff1a; 《自动驾驶新人之旅》免费课程—> 传送门 《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 多态的概念 通俗来说就是多种形态&#xff0c;具体点就是去完成某个行为&#xff0c;当…...

玩转ansible之参数调试和文件操作篇

更多IT技术文章&#xff0c;欢迎关注微信公众号“运维之美” 玩转ansible之参数调试和文件操作篇 01 剧本调试和帮助02 使用场景举例 上节我们学习了使用ansible进行软件安装&#xff0c;那么安装完软件后&#xff0c;就需要linux系统和软件配置修改了&#xff0c;对于linux主机…...

JVM虚拟机:垃圾回收器之Parallel Old(老年代)

本文重点 本文将学习老年代的另外一种垃圾回收器Parallel Old(PO)&#xff0c;这是一种用于老年代的并行化垃圾回收器&#xff0c;它使用标记整理算法进行垃圾回收。 历史 在1.6之前&#xff0c;新生代使用Parallel Scavenge只能搭配老年代的Serial Old收集器&#xff0c;而…...

Stream流的groupingBy

Stream流的groupingBy 简单使用 业务场景&#xff1a;现在有100个人&#xff0c;这些人都年龄分部在18-30岁之间。现要求把他们按照年龄进行分组 key&#xff1a;年龄 value&#xff1a;数据列表 public void listToMapGroup() {//这里假设通过listStreamService.list();方法…...

如何在不结束tcpdump的情况下复制完整的pcap

tcpdump正在运行的时候&#xff0c;他写入的pcap可能是不完整的&#xff0c;通常我们要结束掉tcpdump才能拿到完整的pcap&#xff0c;否则wireshark打开的时候会提示&#xff1a;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)

目录 一批处理。 &#xff08;1&#xff09;批处理定义。 &#xff08;2&#xff09;常见命令。 &#xff08;2.1&#xff09;rem和:: &#xff08;2.2&#xff09;echo和。 &#xff08;2.3&#xff09;pause。 &#xff08;2.4&#xff09;errorlevel。 &#xff08;…...

给数学恐惧者的图解:用几何直觉理解SVM中的对偶问题与KKT条件

给数学恐惧者的图解&#xff1a;用几何直觉理解SVM中的对偶问题与KKT条件 第一次接触支持向量机&#xff08;SVM&#xff09;时&#xff0c;很多人都会被"对偶问题"和"KKT条件"这两个概念吓退。教科书上密密麻麻的数学推导让人望而生畏&#xff0c;仿佛在提…...

Spotify广告拦截终极方案:BlockTheSpot深度技术解析与实战指南

Spotify广告拦截终极方案&#xff1a;BlockTheSpot深度技术解析与实战指南 【免费下载链接】BlockTheSpot Video, audio & banner adblock/skip for Spotify 项目地址: https://gitcode.com/gh_mirrors/bl/BlockTheSpot 在享受Spotify免费音乐服务时&#xff0c;无休…...

生成式AI时代的产品创新:以AI Agent为核心功能的下一代APP设计

生成式AI时代的产品创新:以AI Agent为核心功能的下一代APP设计 1. 引入与连接 1.1 一个引人入胜的未来场景 想象一下,2025年的一个普通早晨: 你的手机闹钟响起,但这不是预设好的固定时间,而是你的"私人生活助理"AI Agent根据你的睡眠质量、当天日程和天气情…...

Multisim14仿真进阶:单管共射放大电路参数扫描与性能优化实战

1. 单管共射放大电路基础与Multisim14环境搭建 单管共射放大电路是模拟电路学习的经典案例&#xff0c;它就像电子世界的"扩音器"&#xff0c;能把微弱的电信号放大到我们需要的强度。在Multisim14这个电子工程师的"虚拟实验室"里&#xff0c;我们可以安全…...

MicroPython中断处理实战:如何避免内存分配陷阱(附代码示例)

MicroPython中断处理实战&#xff1a;如何避免内存分配陷阱&#xff08;附代码示例&#xff09; 嵌入式开发者在使用MicroPython进行硬件编程时&#xff0c;中断处理是不可或缺的核心技术。然而&#xff0c;许多开发者都曾遇到过这样的困境&#xff1a;精心设计的中断服务程序(…...

别再让CPU等外设了!用Multi-Layer AHB搭建一个不堵车的片上‘高速公路网’

用Multi-Layer AHB构建片上系统的高效数据通道 堵在早高峰的高架桥上时&#xff0c;你有没有想过——芯片里的数据流其实也面临着类似的拥堵问题&#xff1f;当多个处理器核心、DMA控制器同时争抢总线带宽时&#xff0c;传统的单层AHB架构就像只有两条车道的城市主干道&#xf…...

AI Coding Agents 的“生产级技能包”

AI Coding Agents 的“生产级技能包” &#x1f3af; 一、项目定位与核心理念 项目名称&#xff1a;agent-skills 维护者&#xff1a;Addy Osmani 目标用户&#xff1a;Claude Code、Cursor、Gemini CLI、Windsurf 等 AI 编码代理 核心思想&#xff1a;Skills encode the workf…...

深入解析Android malloc_debug:内存调试利器的工作原理与实践指南

1. Android内存调试的痛点与解决方案 在Android应用开发过程中&#xff0c;Native层内存问题一直是开发者最头疼的问题之一。不同于Java层有完善的垃圾回收机制&#xff0c;Native层的内存管理完全依赖开发者手动控制&#xff0c;这就容易导致各种内存问题。我见过太多因为Nati…...

告别复杂模拟电路!用STC8G1K17单片机PWM+DAC实现信号转换,保姆级教程

用STC8G1K17单片机实现高精度信号转换的工程实践 在电子设计领域&#xff0c;模拟电路一直是信号处理的核心手段。然而&#xff0c;随着微控制器性能的不断提升&#xff0c;越来越多的传统模拟电路功能可以通过数字方式实现。这种"软件替代硬件"的思路不仅能大幅简化…...

射频滤波器设计实战:从理论原型到电路实现

1. 射频滤波器设计入门&#xff1a;从理论到实践的桥梁 第一次接触射频滤波器设计时&#xff0c;我被各种专业术语和数学公式搞得晕头转向。直到有一次&#xff0c;我在调试一个2.4GHz的Wi-Fi模块时&#xff0c;发现信号中混入了大量的邻频干扰&#xff0c;这才意识到滤波器设…...