【LeetCode】数据结构题解(9)[复制带随机指针的链表]

复制带随机指针的链表

  • 😉 1.题目来源
  • 👀2.题目描述
  • 🤔3.解题思路
  • 🥳4.代码展示

在这里插入图片描述

所属专栏:玩转数据结构题型❤️
🚀 >博主首页:初阳785❤️
🚀 >代码托管:chuyang785❤️
🚀 >感谢大家的支持,您的点赞和关注是对我最大的支持!!!❤️
🚀 >博主也会更加的努力,创作出更优质的博文!!❤️
🚀 >关注我,关注我,关注我,重要的事情说三遍!!!!!!!!❤️

😉 1.题目来源

LeetCode:复制带随机指针的链表

👀2.题目描述

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

在这里插入图片描述

🤔3.解题思路

  • 我们分析一下题目的要求:复制一个长度为n的链表,其中节点里面包含了一个val值和一个random随机指针,这个指针可指向链表中的任意一个节点包括了NULL。
  • 如果题目只是要求复制一个长度为n的链表,并且复制val值的话就简单的多了。直接遍历原链表,把值都一一复制过来就行了。但是题目多加了一个条件,就是random值。复制节点的值很简单,😔但是random是一个指向节点的指针,当我们复制链表的时候,我们新的链表节点的地址肯定是与原链表节点的地址是不一样的,即使遍历了原链表的random值也找不到新链表的random值,🙅 所以找到random值是一个难点。
  • 那既然这样我们便可以创建一个长度为n+1的整形数组,用来记录每个节点距离头节点的距离包括了NULL。这样的话我们就可以先遍历原链表,把每个节点random所指向的值计入到数组当中,然后复制链表的时候,🤩根据这个数组来找到random指向的值。这固然是一种方法,但是他的 空间复杂度:O(n)时间复杂度:O(n^2),并不是一个好的解题方法。
  • 🤔那怎么才可以在遍历原数组的过程中就可以确定复制链表的random值呢?那我们就可以从原链表出发。🤯于是我们就想到了,如果我们把每个要复制的节点都插入到被复制节点的后面(也就是每个原节点的后面)这样的话,就很好的解决了找random值这一问题。我们原节点->random->next == 复制节点->random。

在这里插入图片描述

  • 完成复制与以及给random赋值完后,就可以把复制节点断开,一一链接成链表,并且恢复原链表
    在这里插入图片描述

🥳4.代码展示

struct Node* copyRandomList(struct Node* head) 
{//第一步,把每个拷贝节点链接到原节点出struct Node* cur = head;while (cur){struct Node* Next = cur->next;//开辟赋值节点struct Node* copyNode = (struct Node*)malloc(sizeof(struct Node));//给节点拷贝val值copyNode->val = cur->val;cur->next = copyNode;copyNode->next = Next;cur = Next;}//第二步,给random赋值cur = head;while (cur){struct Node* copyNode = cur->next;if (cur->random == NULL){copyNode->random = NULL;}else{copyNode->random = cur->random->next;}cur = copyNode->next;}//第三步,链接赋值链表,并恢复原链表cur = head;struct Node* copyhead = NULL, *copyCur = NULL;while (cur){struct Node* copy = cur->next;struct Node* Next = copy->next;if (copyhead == NULL){copyhead = copyCur = copy;}else{copyCur->next = copy;copyCur = copyCur->next;}cur->next = Next;cur = Next;}return copyhead;}

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

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

相关文章

el-select与el-tree结合使用,实现select框下拉使用树形结构选择数据

使用el-select与el-tree&#xff0c;实现如下效果&#xff0c; 代码如下&#xff1a; 注意点&#xff1a;搜索input框的代码一点放在option上面&#xff0c;不要放在option里面&#xff0c;否则一点击搜索框&#xff0c;下拉框就会收起来&#xff0c;不能使用。 <el-select…

wxwidgets Ribbon使用wxRibbonToolBar实例

wxRibbonToolBar就是工具栏&#xff0c;一下是实现的效果&#xff0c;界面只是功能展示&#xff0c;没有美化 实现代码如下所示&#xff1a; MyFrame::MyFrame(const wxString& title) : wxFrame(NULL, wxID_ANY, title, wxDefaultPosition, wxSize(800, 600)) …

锐捷VSU技术理论与实验

目录 VSU涉及的相关基础概念 VSU的2种工作模式 VSU的3种设备角色 VSU的4种设备状态 VSU的分裂与合并 VSU建立过程 双主检测 VSU报文转发原理 VSU命令配置 配置VSU 配置双主检测 VSU涉及的相关基础概念 域编号&#xff08;Domain ID&#xff09; Domain ID是VSU的标…

【C++】bind包装器

bind包装器 调用bind的一般形式&#xff1a;auto newCallable bind(callable,arg_list); 其中&#xff0c;newCallable本身是一个可调用对象&#xff0c;arg_list是一个逗号分隔的参数列表&#xff0c;对应给定的 callable的参数。 当我们调用newCallable时&#xff0c;newCa…

【硬件设计】模拟电子基础三--集成运算放大电路

模拟电子基础三--集成运算放大电路 一、集成运算放大器1.1 定义、组成与性能1.2 电流源电路1.3 差动放大电路1.4 理想运算放大器 二、集成运算放大器的应用2.1 反向比例运算电路2.2 同向比例运算电路2.3 反向加法运算电路2.4 反向减法运算电路2.5 积分运算电路2.6 微分运算电路…

数据结构【图的类型定义和存储结构】

数据结构之图 图的定义和概念图的定义图的术语 图的类型定义图的存储结构数组&#xff08;邻接矩阵&#xff09;表示法无向图的邻接矩阵表示法有向图的邻接矩阵表示法网&#xff08;即有权图&#xff09;的邻接矩阵表示法 邻接矩阵的ADT定义邻接表&#xff08;链式&#xff09;…

opencv-32 图像平滑处理-高斯滤波cv2.GaussianBlur()

在进行均值滤波和方框滤波时&#xff0c;其邻域内每个像素的权重是相等的。在高斯滤波中&#xff0c;会将中心点的权重值加大&#xff0c;远离中心点的权重值减小&#xff0c;在此基础上计算邻域内各个像素值不同权重 的和。 基本原理 在高斯滤波中&#xff0c;卷积核中的值不…

【图像去噪】基于进化算法——自组织迁移算法(SOMA)的图像去噪研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

vue3实现自定义select下拉框内容之城市区域篇

分享-2023年资深前端进阶&#xff1a;前端登顶之巅-最全面的前端知识点梳理总结 *分享一个使用比较久的&#x1fa9c; 需求分析&#xff1a; 1、实现一个区域下拉选项与现有ui组件库不同&#xff0c;支持多选、单选需求 2、支持选中区域后-全选中当前区域下的所有城市信息 3、…

项目实战 — 消息队列(5){统一硬盘操作}

前面已经使用数据库管理了交换机、绑定、队列&#xff0c;然后又使用了数据文件管理了消息。 那么&#xff0c;这里就创建一个类&#xff0c;讲之前的两个部分整合起来&#xff0c;对上层提供统一的一套接口&#xff0c;表示硬盘上存储的所有的类的信息。 /* * 用这个类来管理…

企业计算机服务器中了locked勒索病毒怎么办,如何预防勒索病毒攻击

计算机服务器是企业的关键信息基础设备&#xff0c;随着计算机技术的不断发展&#xff0c;企业的计算机服务器也成为了众多勒索者的攻击目标&#xff0c;勒索病毒成为当下计算机服务器的主要攻击目标。近期&#xff0c;我们收到很多企业的求助&#xff0c;企业的服务器被locked…

Unico-GUI软件关于ST传感器机器学习(MLC)基本操作步骤

准备工作 UNICO-GUI软件用于意法半导体产品组合&#xff08;加速度计、陀螺仪、磁力计和环境传感器&#xff09;中所有MEMS传感器的评估板。它可用于Linux&#xff08;基于Debian&#xff09; / Mac OS X / Windows平台。 Unico-GUI - MEMS evaluation kit software package …

优维低代码实践:对接数据

优维低代码技术专栏&#xff0c;是一个全新的、技术为主的专栏&#xff0c;由优维技术委员会成员执笔&#xff0c;基于优维7年低代码技术研发及运维成果&#xff0c;主要介绍低代码相关的技术原理及架构逻辑&#xff0c;目的是给广大运维人提供一个技术交流与学习的平台。 优维…

工厂方法模式-java实现

介绍 工厂方法模式&#xff0c;通过把工厂抽象为一个接口&#xff0c;这样当我们新增具体产品的时候&#xff0c;就只需要实现一个新的具体工厂类即可。一个具体工厂类&#xff0c;对应着一个产品。 请注意&#xff1a;在工厂方法模式中&#xff0c;一个具体工厂类只对应生产…

Android 数据库之GreenDAO

GreenDAO 是一款开源的面向 Android 的轻便、快捷的 ORM 框架&#xff0c;将 Java 对象映射到 SQLite 数据库中&#xff0c;我们操作数据库的时候&#xff0c;不再需要编写复杂的 SQL语句&#xff0c; 在性能方面&#xff0c;greenDAO 针对 Android 进行了高度优化&#xff0c;…

四、web应用程序技术——HTTP

文章目录 1 HTTP请求2 HTTP响应3 HTTP方法4 URL5 HTTP消息头5.1 常用消息头5.2 请求消息头5.3 响应消息头 6 cookie7 状态码8 HTTP代理9 HTTP身份验证 HTTP&#xff08;HyperText Transfer Protocol&#xff0c;超文本传输协议&#xff09;是访问万维网使用的核心通信协议&…

Sentieon | 每周文献-Multi-omics(多组学)-第九期

多组学系列文章-1 标题&#xff08;英文&#xff09;&#xff1a; Prediction of axillary lymph node metastasis in triple-negative breast cancer by multi-omics analysis and an integrated model标题&#xff08;中文&#xff09;&#xff1a; 基于多组学分析和综合模型…

Spark Catalog详解

前言 旁边的实习生说:我想要用spark代码中对hive库中的内部表和外部表进行批量删除(包括数据),咋感觉网上搜了一圈都找不到解决方案啊,spark这么鸡肋吗? 我:你应该静下心来好好把spark基础知识进行全面学习。 实习生:难道spark有这功能,而我没有学习过?咋弄啊? 我:…

STM32基础入门学习笔记:开发板 电路原理与驱动编程

文章目录&#xff1a; 一&#xff1a;触摸按键 1.触摸按键驱动程序&#xff08;点击&#xff09; touch_key.h touch_key.c main.c 2.按键双击和长按程序 touch_key.h touch_key.c main.c 3.触摸按键滑动程序 main.c 二&#xff1a;数码管显示 1.数码管RTC时钟LE…

JAVA电商平台免费搭建 B2B2C商城系统 多用户商城系统 直播带货 新零售商城 o2o商城 电子商务 拼团商城 分销商城 bbc

​ 1. 涉及平台 平台管理、商家端&#xff08;PC端、手机端&#xff09;、买家平台&#xff08;H5/公众号、小程序、APP端&#xff08;IOS/Android&#xff09;、微服务平台&#xff08;业务服务&#xff09; 2. 核心架构 Spring Cloud、Spring Boot、Mybatis、Redis 3. 前…