【数据结构】链表OJ面试题5《链表的深度拷贝》(题库+解析)
1.前言
前五题在这http://t.csdnimg.cn/UeggB
后三题在这http://t.csdnimg.cn/gbohQ
给定一个链表,判断链表中是否有环。http://t.csdnimg.cn/Rcdyc
给定一个链表,返回链表开始入环的第一个结点。 如果链表无环,则返回 NULLhttp://t.csdnimg.cn/pbFiK
记录每天的刷题,继续坚持!
2.OJ题目训练
11. 给定一个链表,每个结点包含一个额外增加的随机指针,该指针可以指向链表中的任何结点或空结点。 要求返回这个链表的深度拷贝。力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
题目分析
给你一个长度为
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作为传入参数。
这道题第一次做还是会有点理解的...但其实也不复杂
其实就是,一个正常的单链表,但是有数据位,也能有指向下一个节点位,但是多出来一个指针会随机指向此链表的如何一个节点,而我们就要对他进行一个复制。复制单链表简单,但是我们要注意,这里还增加了一个额外的指针。而且我们复制的时候随机指针还是要指向原本对应的节点。
比如:下面的d1的随机指针指向了d3,而我们新的d1节点就要指向新的d3节点

若我们直接暴力复制原链表的所有值,就会发生这种错误情况

所以此题不能暴力求解。
方法
1.首先先把拷贝节点放在每个原节点后面,这样子就可以很好的查找各节点的random

2.置每个拷贝的节点random,因为我们可以依据相对位置找到原节点的random,再让他赋值

copy->random = cur->random->next //拷贝random节点的关键代码
3.收尾工作:拷贝的节点和原节点分开,恢复原链表。
附源代码
/*** 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));struct Node* Next = cur->next;copy->val = cur->val;//插入copycur->next = copy;copy->next = Next;//往后走 cur = Next;}//重新开始走,因为random的特殊性//所以在copy节点没有全部创造出来还不能添加cur = head;while(cur){ struct Node* copy = cur->next;//置 copy randomif(cur->random == NULL) //考虑其中一种为0的情况,如果为NULL访问就会报错{copy->random = NULL;}else{copy->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 = cur->next->next;if(copytail == NULL){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copytail->next;} cur->next = next;cur = next;}return copyhead;
}
12. 其他 。ps:链表的题当前因为难度及知识面等等原因还不适合我们当前学习,可以自行练习。
力扣
牛客网在线编程_算法篇_面试必刷TOP101
相关文章:
【数据结构】链表OJ面试题5《链表的深度拷贝》(题库+解析)
1.前言 前五题在这http://t.csdnimg.cn/UeggB 后三题在这http://t.csdnimg.cn/gbohQ 给定一个链表,判断链表中是否有环。http://t.csdnimg.cn/Rcdyc 给定一个链表,返回链表开始入环的第一个结点。 如果链表无环,则返回 NULLhttp://t.cs…...
智慧校园规划建设方案
校园信息化建设呈现智能化、应用多样化发展趋势,多种技术和应用交叉渗透至校园生活的各个方面,全面的智慧校园时代已经到来。 对智慧校园的四大应用领域分析 智慧的教学 信息共享交互:建立信息发布、共享、传播与交互的公共平台 教学流程…...
003 - Hugo, 创建文章
003 - Hugo, 创建文章创建文章单个md文件md文件图片总结 文章内容Front Matter文章目录数学公式的显示KaTeXMathJax 图片 003 - Hugo, 创建文章 创建文章 单个md文件 创建文章的方式: 手动创建:在post目录下,手动创建md文件。命令创建&am…...
HCIA-HarmonyOS设备开发认证V2.0-IOT硬件子系统-GPIO
目录 一、GPIO 概述二、GPIO模块相关API三、实例四、GPIO HDF驱动开发4.1、LED驱动程序(待续...)4.2、LED驱动配置(待续...) 坚持就有收获 轻量系统设备通常需要进行外设控制,例如温湿度数据的采集、灯开关的控制,因此在完成内核开发后,需要进…...
《Java 简易速速上手小册》第7章:Java 网络编程(2024 最新版)
文章目录 7.1 网络基础和 Java 中的网络 - 揭开神秘的面纱7.1.1 基础知识7.1.2 重点案例:实现一个简单的聊天程序7.1.3 拓展案例 1:使用 UDP 进行消息广播7.1.4 拓展案例 2:建立一个简单的 Web 服务器 7.2 创建客户端和服务器 - 构建沟通的桥…...
用keras对电影评论进行情感分析
文章目录 下载IMDb数据读取IMDb数据建立分词器将评论数据转化为数字列表让转换后的数字长度相同加入嵌入层建立多层感知机模型加入平坦层加入隐藏层加入输出层查看模型摘要 训练模型评估模型准确率进行预测查看测试数据预测结果完整函数用RNN模型进行IMDb情感分析用LSTM模型进行…...
每日OJ题_算法_递归④力扣24. 两两交换链表中的节点
目录 ④力扣24. 两两交换链表中的节点 解析代码 ④力扣24. 两两交换链表中的节点 24. 两两交换链表中的节点 难度 中等 给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即…...
110 C++ decltype含义,decltype 主要用途
一,decltype 含义和举例 decltype有啥返回啥,auto则不一样,auto可能会舍弃一些东西。 decltype 是 C11提出的说明符。主要作用是:返回操作数的数据类型。 decltype 是用来推导类型,decltype对于一个给定的 变量名或…...
PYTHON 120道题目详解(85-87)
85.Python中如何使用enumerate()函数获取序列的索引和值? enumerate()函数是Python的内置函数,它可以将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列,同时列出数据和数据下标,一般用在for循环当中。 以下是一个…...
【Linux】Linux编译器-gcc/g++ Linux项目自动化构建工具-make/Makefile
目录 Linux编译器-gcc/g使用 1.背景知识 Linux中头文件的目录在 Linux 库 条件编译的典型应用 2.gcc如何完成 动态库 vs 静态库 debug && release Linux项目自动化构建工具-make/Makefile 背景 用法 特殊符号 Linux编译器-gcc/g使用 1.背景知识 预处理&am…...
sqlserver 子查询 =,in ,any,some,all的用法
在 SQL Server 中,子查询常用于嵌套在主查询中的子句中,以便根据子查询的结果集来过滤主查询的结果,或者作为主查询的一部分来计算结果。 以下是 、IN、ANY、SOME 和 ALL 运算符在子查询中的用法示例: 使用 运算符进行子查询&a…...
基于MapVGL的地理信息三维度数据增长可视化
写在前面 工作中接触,简单整理博文内容为 基于MapVGL的地理信息维度数据增长可视化 Demo理解不足小伙伴帮忙指正 对每个人而言,真正的职责只有一个:找到自我。然后在心中坚守其一生,全心全意,永不停息。所有其它的路都…...
天锐绿盾|防泄密系统|计算机文件数据\资料安全管理软件
“天锐绿盾”似乎是一款专注于防泄密和计算机文件数据/资料安全管理的软件。在信息安全日益受到重视的今天,这样的软件对于保护企业的核心数据资产和防止敏感信息泄露至关重要。 通用地址:www.drhchina.com 防泄密系统的主要功能通常包括: 文…...
leetcode刷题(罗马数字转数字)
1.题目描述 2.解题思路 这时候已经给出了字母对应的数字,我们只需要声明一个字典,将罗马数字和数字之间的对应关系声明即可。其中可能涉及到会出现两个连续的罗马字母代表一个数字,这时候我们需要判断遍历的字符和将要遍历的下一个字符是否存…...
什么是NAT网关?联通云NAT网关有什么优势
在当今云计算时代,网络安全和连接性是企业发展的关键因素之一。NAT网关(Network Address Translation Gateway)是一种网络设备,它可以在私有网络和公共网络之间进行地址转换,从而使得内部网络中的设备能够与外部网络进…...
CVE-2023-41892 漏洞复现
CVE-2023-41892 开题,是一个RCE Thanks for installing Craft CMS! You’re looking at the index.twig template file located in your templates/ folder. Once you’re ready to start building out your site’s front end, you can replace this with someth…...
【每日一题】06 排序链表
问题描述 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。 求解 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode* sortList(struct ListNode* head) {struct…...
【精品】关于枚举的高级用法
枚举父接口 public interface BaseEnum {Integer getCode();String getLabel();/*** 根据值获取枚举** param code* param clazz* return*/static <E extends Enum<E> & BaseEnum> E getEnumByCode(Integer code, Class<E> clazz) {Objects.requireNonN…...
Vue2学习第一天
Vue2 学习第一天 1. 什么是 vue? Vue 是一套用于构建用户界面的渐进式框架。 2. vue 历史 vue 是在 2013 年创建的,vue3 是 2020 出现的,现在主要是用 vue2,创新公司用的是 vue3 vue 的作者是尤雨溪,vue 的搜索热度比 react…...
HAL STM32通过multi_button库处理按键事件
HAL STM32通过multi_button库处理按键事件 📍作者:0x1abin的multi_button库:https://github.com/0x1abin/MultiButton 📘MultiButton简介 MultiButton 是一个小巧简单易用的事件驱动型按键驱动模块,可无限量扩展按键,…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
