【基础算法】单链表的OJ练习(6) # 复制带随机指针的链表 #
文章目录
- 🍇前言
- 🍎复制带随机指针的链表
- 🍑写在最后
🍇前言
-
本章的链表
OJ练习,是最后的也是最难的。对于本题,我们不仅要学会解题的思路,还要能够通过这个思路正确的写出代码,也就是思路转化为代码的过程,这应该就是最难的地方了吧。 -
对于OJ练习(5): -> 传送门 <-,环形链表的做法的证明一定要理解透彻,因为面试很可能问到噢。
🍎复制带随机指针的链表
-
题目链接:-> 传送门 <-。
-
题目描述:给你一个长度为
n的链表,每个节点包含一个额外增加的随机指针random,该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由n个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如:如果原链表中有X和Y两个节点,其中X.random --> Y。那么在复制链表中对应的两个节点x和y,同样有x.random --> y。返回复制链表的头节点。 -
也就是复制一个链表。
例如复制下面这个链表:(复制后返回复制后的链表的头节点)

解题思路:
-
我相信,看到这个题,第一感觉就是暴力把他给复制了。但暴力终会达到
O(N^2),虽然可以过,但如果面试的时候遇到这个问题,面试官可能就会问:如何将时间复杂度降到O(N)呢? -
所以这里使用一种
O(N)的方法来解这道题。 -
首先,我们在原链表上的每一个节点后面插入一个与自己有相同值的节点(称为
copy节点),然后进行连接,如下:

- 然后进行的操作是最关键的:再遍历一遍连接了
copy节点后的链表,将每一个copy节点的random指向它前一个节点(就是被复制的那个节点,因此这里操作的时候,需要一个指针指向copy节点的前一个节点)的random的next节点,如果copy的前一个节点的random指向NULL,那直接将copy节点的random指向NULL,直到遍历结束,可以得到下面这个链表:

-
细心观察不难发现,上面的所有
copy节点组成的链表实际上就与原链表相同了。 -
因此最后的操作,就是将每一个
copy节点取下来尾插到新的链表上,最后返回这个新链表的头即可。当然啦,这里还需要将原链表复原。 -
根据上面的思路,会发现,如何将这些过程转换成代码是个难点。这里没得巧,就是多练,多写,正如:无他,唯手熟尔。
⏩下面是代码实现(注意:一边写代码或者看代码,一边要体会整个思路的过程):
struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;while (cur){// 创建copy节点struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;// 存放当前节点的下一个节点的地址,便于连接和继续遍历链表struct Node* next = cur->next;// 连接cur->next = copy;copy->next = next;cur = next;}cur = head;while (cur){// 同样三个指针遍历struct Node* copy = cur->next;struct Node* next = copy->next;// 放置copy的random指针if (cur->random == NULL) copy->random = NULL;else copy->random = cur->random->next;cur = next;}// 新链表的头和连接新链表的指针struct Node* copyHead = NULL, *copyTail = NULL;cur = head;while (cur){// 同样需要三个指针来遍历struct Node* copy = cur->next;struct Node* next = copy->next;// 如果copyHead为NULL,先同时指向头节点if (copyHead == NULL) {copyHead = copyTail = copy;}else {copyTail->next = copy;copyTail = copyTail->next;}// 复原原链表cur->next = next;// 找下一个cur = next;}return copyHead;
}
🍑写在最后
对于单链表的题目练习,最重要的是思路,我们在数据结构阶段要养成画图的习惯,因为它能帮助我们更好的理解。单链表的OJ练习在此就结束了,大家要好好练习噢~
感谢阅读本小白的博客,错误的地方请严厉指出噢~
相关文章:
【基础算法】单链表的OJ练习(6) # 复制带随机指针的链表 #
文章目录🍇前言🍎复制带随机指针的链表🍑写在最后🍇前言 本章的链表OJ练习,是最后的也是最难的。对于本题,我们不仅要学会解题的思路,还要能够通过这个思路正确的写出代码,也就是思路…...
Activity生命周期完成EvenetLog回调
Activity 生命周期 系统EvenetLog回调 EventLog路径: Android13/frameworks/base/core/java/android/app/EventLogTags.logtags wm_on_create_called wm_on_restart_called wm_on_start_called wm_on_resume_called wm_on_top_resumed_gained_called wm_on_top_resumed_lost_c…...
西安石油大学C语言期末真题实战
很简单的一道程序阅读题,pa’默认为a【0】,接下来会进行3次循环 0 1 2 输出结果即可 前3题就是一些基础定义,在此不多赘述 要注意不同的数据类型的字节数不同 a<<2 b>>1(b>>1;就是说b自身右位移一位(…...
【Shell】Shell变量
Shell变量系统预定义变量自定义变量基本语法定义变量撤销变量命名规则使用变量只读变量删除变量变量类型系统预定义变量 $HOME、$PWD、$SHELL、$SUSER等 实例 yysubuntu:~$ echo $HOME #查看系统变量的值 /home/yys yysubuntu:~$ set #显示当前shell中所有变量自定义变量…...
你是真的“C”——结构体中鲜有人知的“秘密”
你是真的“C”——结构体中的精髓剖析【内存对齐】 【位段】 😎前言🙌结构体内存对齐:😊结构体内存对齐存在的意思是什么?😘内存对齐例子详细剖析:😘结构体中的位段:&…...
2023年“网络安全”赛项江苏省淮安市赛题解析(超详细)
2023年中职组江苏省淮安市“网络空间安全”赛项 ①.2023年中职组江苏省淮安市任务书②.2023年中职组江苏省淮安市解析③.需要环境或者不懂的可以私信博主!①.2023年中职组江苏省淮安市任务书 任务一:服务器内部信息获取 任务环境说明: 服务器场景:Server210510(关闭链接…...
【二分查找】
二分查找704. 二分查找35. 搜索插入位置34. 在排序数组中查找元素的第一个和最后一个位置结语704. 二分查找 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在…...
Vue学习 -- 如何用Axios发送请求(get post)Promise对象 跨域请求问题
什么是Axios Vue本身是不支持发送axios请求,需要使用第三方插件,这里推荐使用Axios,Axios是基于promise的HTTP库;它会从浏览器中创建XMLHttpRequset对象。 安装Axios npm install axios -S下载后把axios.js文件复制进项目目录 …...
TVS和稳压管的相同点和不同点
大家好,我是记得诚。 文章目录 介绍相同点不同点介绍 TVS和稳压管都是电路中很常用的电子元器件,都是二极管的一个种类。 TVS二极管全称是Transient voltage suppression diode,也叫瞬态电压抑制二极管。 稳压二极管英文名字Zener diode,又叫齐纳二极管。 关于稳压二极…...
微信小程序项目实例——扫雷
今日推荐💁♂️ 2023许嵩演唱会即将到来🎤🎤🎤大家一起冲冲冲🏃♂️🏃♂️🏃♂️ 🔮🔮🔮🔮🔮往期优质项目实例🔮…...
2022-2023年度广东省职业院校学生专业技能大赛 中职组网络安全赛项竞赛规程
2022-2023年度广东省职业院校学生专业技能大赛 中职组网络安全赛项竞赛规程 一、赛项名称 赛项编号:Z27 赛项名称:网络安全赛项组别:中职 赛项归属:信息技术类 二、竞赛目的 为检验中职学校网络信息安全人才培养成效,促…...
超详细的堆排序,进来看看吧。
1.堆的基本概念1.1什么是堆堆是一种叫做完全二叉树的数据结构,1.2大堆和小堆大堆:每个节点的值都大于或者等于他的左右孩子节点的值小根堆:每个结点的值都小于或等于其左孩子和右孩子结点的值1.3完全二叉树节点之间的关系leftchild parent*2 1rightchild parent*…...
线性回归 特征扩展的原理与python代码的实现
文章目录1 多项式扩展的作用2 多项式扩展的函数2.1 接收参数2.2 多项式扩展示例3 多项式扩展的完整实例1 多项式扩展的作用 在线性回归中,多项式扩展是种比较常见的技术,可以通过增加特征的数量和多项式项的次数来提高模型的拟合能力。 举个例子&#…...
订阅关系一致
订阅关系一致指的是同一个消费者Group ID下所有Consumer实例所订阅的Topic、Tag必须完全一致。如果订阅关系不一致,消息消费的逻辑就会混乱,甚至导致消息丢失。本文提供订阅关系一致的正确示例代码以及订阅关系不一致的可能原因,帮助您顺畅地订阅消息。 背景信息 消息队列Ro…...
测试老鸟都在用的接口抓包常用工具以及接口测试工具都有哪些?
目录 接口 接口测试的重要性 常用抓包工具 常用接口测试工具 接口 接口测试是测试系统组件间接口的一种测试。接口测试主要用于检测外部系统与系统之间以及内部各个子系统之间的交互点。测试的重点是要检查数据的交换,传递和控制管理过程,以及系统间…...
Delphi 一个函数实现腾讯云最新版(API3.0)短信发送
目录 一、腾讯云短信基本知识 1. 需要在腾讯云后台注册账号 2. 需要在腾讯云中开通短信功能 3. 腾讯云短信版本说明 4. 短信内容的组成 特定规范 二、短信发送函数 三、下载源代码(收费) 一、腾讯云短信基本知识 如今我们随时都收到短信验证码,注册码等等。这是…...
2023年Android现代开发
2023年现代Android开发 下面与大家分享如何构建具有2023年最新趋势的Android应用程序。 Android是什么? Android 是一种基于 Linux 内核并由 Google 开发的开源操作系统。它用于各种设备,包括智能手机、平板电脑、电视和智能手表。 目前,…...
自然语言处理(NLP)在医疗领域的应用
自然语言处理(Natural Language Processing,NLP)是计算机科学领域与人工智能领域中的一个重要方向。它研究能实现人与计算机之间用自然语言进行有效通信的各种理论和方法。在各个领域都有其应用。 其在生物医学领域迅速发展,已经…...
计算机中的浮点数运算
计算机中的浮点数 计算机中以固定长度存储浮点数的方式,造成了浮点数运算过程容易产生上溢和下溢。以float32为例, 其标记位占1bit,指数位占8bit,小数部分占23bit 经典下溢场景 不满足精度导致截断误差 #include <iostream> #include <iomanip> usin…...
看了字节跳动月薪20K+测试岗面试题,让我这个工作3年的测试工程师,冷汗直流....
朋友入职已经两周了,整体工作环境还是非常满意的!所以这次特意抽空给我写出了这份面试题,而我把它分享给伙伴们,面试&入职的经验! 大概是在2月中的时候他告诉我投递了字节跳动并且简历已通过,2月23经过…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...
