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

Leetcode138. 复制带随机指针的链表

复制带随机指针的链表

第一步 拷贝节点链接在原节点的后面
第二步拷贝原节点的random , 拷贝节点的 random 在原节点 random 的 next
第三步 将拷贝的节点尾插到一个新链表 ,并且将原链表恢复

从前往后遍历链表 ,将原链表的每个节点进行复制,并l链接到原节点的后面
malloc 一个节点copy

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

cur 往后走 ,不能写成cur =cur->next ,因为已经改变了链接关系,找不到cur的下一个节点的地址了

第一步的代码

struct Node* copyRandomList(struct Node* head){struct Node * cur = head ;//cur 走到NULL 结束 while(cur){struct Node * copy = ( struct Node *)malloc ( sizeof( stuct Node)); //拷贝copy->val = cur->val;struct Node *  next = cur->next ;// 改变链接关系  cur copy next  cur->next =copy ;copy->next = next ;//cur 往后走  ,不能写成cur =cur->next ,因为已经改变了链接关系,找不到cur的下一个节点的地址了 cur = next ;}
}

对原链表 random 指针的复刻 , 即原节点 的 random 拷贝到 拷贝节点 的 random 里面

在这里插入图片描述

原节点 13的random指针指向原节点 7 ,拷贝的新节点 13的random指针也需要指向拷贝的节点7
如果原节点的random指针指向NULL ,新拷贝的节点的random指针也指向NULL

第二步的代码

//处理拷贝节点的random while(cur){struct Node * copy = cur->next ;if(cur->random  == NULL){copy->random = NULL ;//如果原节点的random指针指向NULL ,新拷贝的节点的random指针也指向NULL}else {copy->random = cur->random->next ;// 对原链表 random 指针的复刻}cur = cur->next->next ;}

在这里插入图片描述

上图中,我们可以观察到原节点 13的random指针指向原节点 7,拷贝的新节点13的random指针指向的是原节点7的next

推广一下也就是说
原节点 i 的random指针,指向的是原节点 j
那么新拷贝的节点 的random指针,指向的是原节点 j 的 next

但是这样下来 已经破坏了原链表 ,所以下一步是将拷贝的节点尾插到一个新链表 ,并且将原链表恢复

尾插
在这里插入图片描述

恢复原链表
在这里插入图片描述
在这里插入图片描述
第三步代码

    //将拷贝的新节点尾插到一个新链表, 并恢复原链表cur =head ;struct Node * copyhead  = NULL , * copyTail = NULL ;while( cur){   struct Node *   copy =cur->next ;struct Node * next = copy->next ; //尾插if( copyhead ==NULL){copyhead = copyTail = copy ;}else{copyTail->next = copy ;copyTail = copyTail->next ;}//恢复原链表cur->next = next ;cur = next ;}

完整代码

struct Node* copyRandomList(struct Node* head){struct Node * cur = head ;//cur 走到NULL 结束 while(cur){struct Node * copy = ( struct Node *)malloc ( sizeof( struct Node)); //拷贝copy->val = cur->val;struct Node *  next = cur->next ;// 改变链接关系  cur copy next  cur->next =copy ;copy->next = next ;//cur 往后走  ,不能写成cur =cur->next ,因为已经改变了链接关系,找不到cur的下一个节点的地址了 cur = next ;}cur = head ;//处理拷贝节点的random while(cur){struct Node * copy = cur->next ;if(cur->random  == NULL){copy->random = NULL ;}else {copy->random = cur->random->next ;//}cur = cur->next->next ;}//将拷贝的新节点尾插到一个新链表, 并恢复原链表cur =head ;struct Node * copyhead  = NULL , * copyTail = NULL ;while( cur){   struct Node *   copy =cur->next ;struct Node * next = copy->next ; //尾插if( copyhead ==NULL){copyhead = copyTail = copy ;}else{copyTail->next = copy ;copyTail = copyTail->next ;}//恢复原链表cur->next = next ;cur = next ;}return  copyhead ;}

如果你觉得这篇文章对你有帮助,不妨动动手指给点赞收藏加转发,给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力!!

相关文章:

Leetcode138. 复制带随机指针的链表

复制带随机指针的链表 第一步 拷贝节点链接在原节点的后面 第二步拷贝原节点的random , 拷贝节点的 random 在原节点 random 的 next 第三步 将拷贝的节点尾插到一个新链表 ,并且将原链表恢复 从前往后遍历链表 ,将原链表的每个节点进行复制,并l链接到原…...

python并发编程多线程

在传统操作系统中,每个进程有一个地址空间,而且默认就有一个控制线程 线程顾名思义,就是一条流水线工作的过程,一条流水线必须属于一个车间,一个车间的工作过程是一个进程 车间负责把资源整合到一起,是一个…...

使用Maven实现Servlet程序

创建Maven项目我们打开idea的新建项目,选中里面Maven即可,如下图:创建完成之后,会看到这样的目录结构其中,main目录存放业务代码,其中的java目录存放的就是java代码,而resources目录存放是程序中依赖的文件,比如:图片,视频等.然后是 test目录,test目录存放的是测试代码.最后一个…...

百度的文心一言 ,没有想像中那么差

robin 的演示 我们用 robin 的演示例子来对比一下 文心一言和 ChatGPT 的真实表现(毕竟发布会上是录的)。 注意,我使用的 GPT 版本是 4.0 文学创作 1 三体的作者是哪里人? 文心一言: ChatGPT: 嗯&a…...

文心一言发布的个人看法

文心一言发布宣传视频按照发布会上说的,文心一言并非属于百度赶工抄袭Chat-GPT的作品,而是十几年一直布局AI产业厚积薄发的成果,百度在芯片,机器学习,自然语言处理,知识图谱等方面均有相对深厚的积累。 国…...

【C5】111

文章目录bmc_wtd:syscpld.c中wd_en和wd_kick节点对应寄存器,crontab,FUNCNAMEAST2500/2600 WDT切换主备:BMC用WDT2作为主备切换的watchdog控制器AC后读取:bmc处于主primary flash(设完后:实际主…...

静态成员,友元函数

🐶博主主页:ᰔᩚ. 一怀明月ꦿ ❤️‍🔥专栏系列:线性代数,C初学者入门训练,题解C,C的使用文章,「初学」C 🔥座右铭:“不要等到什么都没有了,才下…...

数学分析课程笔记(张平):函数

01 函数 \quad作为数学分析的第一节课,首先深入了解一下函数。 \quad翻看一些教材可以发现,有些教材将“函数”与“映射”区分为两个概念,有些教材(尤其是前苏联时期的一些教材)则将其视为一个概念。实际上&#xff0c…...

spring事务 只读此文

文章目录一. 事务概述1.1. MySQL 数据库事务1.2 spring的事务支持:1.2.1 编程式事务:1.2.2 声明式事务1.2.3 事务传播行为:1.2.4 事务隔离级别1.2.5 事务的超时时间1.2.6 事务的只读属性1.2.7 事务的回滚策略二. spring事务(注解 Transaction…...

真实的软件测试日常工作是咋样的?

最近很多粉丝问我,小姐姐,现在大环境不景气,传统行业不好做了,想转行软件测试,想知道软件测试日常工作是咋样的?平常的工作内容是什么? 别急,今天跟大家细细说一下一个合格的软件测…...

【UML】软件需求说明书

目录🦁 故事的开端一. 🦁 引言1.1编写目的1.2背景1.3定义1.4参考资料二. 🦁 任务概述2.1目标2.2用户的特点2.3假定和约束三. 🦁 需求规定3.1 功能性需求3.1.1系统用例图3.1.2用户登录用例3.1.3学员注册用例3.1.4 学员修改个人信息…...

面试官:html里面哪个元素可以让文字换行展示

在HTML中&#xff0c;可以使用 <br> 元素来强制换行&#xff0c;也可以使用CSS的 word-break 或 white-space 属性来实现自动换行。以下是这些方法的具体说明&#xff1a; 1.使用 <br> 元素 <br> 元素可以在文本中插入一个换行符&#xff0c;使文本从该位置…...

XGBoost和LightGBM时间序列预测对比

XGBoost和LightGBM都是目前非常流行的基于决策树的机器学习模型&#xff0c;它们都有着高效的性能表现&#xff0c;但是在某些情况下&#xff0c;它们也有着不同的特点。 XGBoost和LightGBM简单对比 训练速度 LightGBM相较于xgboost在训练速度方面有明显的优势。这是因为Ligh…...

JVM高频面试题

1、项目中什么情况下会内存溢出&#xff0c;怎么解决&#xff1f; &#xff08;1&#xff09;误用固定大小线程池导致内存溢出 Excutors.newFixedThreadPool内最大线程数是21亿(2) 误用带缓冲线程池导致内存溢出最大线程数是21亿(3)一次查询太多的数据&#xff0c;导致内存占用…...

Windows环境下实现设计模式——状态模式(JAVA版)

我是荔园微风&#xff0c;作为一名在IT界整整25年的老兵&#xff0c;今天总结一下Windows环境下如何编程实现状态模式&#xff08;设计模式&#xff09;。不知道大家有没有这样的感觉&#xff0c;看了一大堆编程和设计模式的书&#xff0c;却还是很难理解设计模式&#xff0c;无…...

【总结】多个条件排序(pii/struct/bool)

目录 pii struct bool pii 现在小龙同学要吃掉它们&#xff0c;已知他有n颗苹果&#xff0c;并且打算每天吃一个。 但是古人云&#xff0c;早上金苹果&#xff0c;晚上毒苹果。由此可见&#xff0c;早上吃苹果和晚上吃苹果的效果是不一样的。 已知小龙同学在第 i 天早上吃苹果能…...

基于stm32mp157 linux开发板ARM裸机开发教程Cortex-A7 开发环境搭建(连载中)

前言&#xff1a;目前针对ARM Cortex-A7裸机开发文档及视频进行了二次升级持续更新中&#xff0c;使其内容更加丰富&#xff0c;讲解更加细致&#xff0c;全文所使用的开发平台均为华清远见FS-MP1A开发板&#xff08;STM32MP157开发板&#xff09;针对对FS-MP1A开发板&#xff…...

最适合游戏开发的语言是什么?

建议初学者学习主流的开发技术 主流开发技术有大量成熟的教程、很多可以交流的学习者、及时的学习反馈等&#xff1b;技术的内里基本都是相同的&#xff0c;学习主流技术的经验、知识可以更好更快地疏通学习新知识和技术。 因此&#xff0c;对C#或者C二选一进行学习较好。 Un…...

C语言刷题(7)(字符串旋转问题)——“C”

各位CSDN的uu们你们好呀&#xff0c;今天&#xff0c;小雅兰的内容依旧是复习之前的知识点&#xff0c;那么&#xff0c;就是做一道小小的题目啦&#xff0c;下面&#xff0c;让我们进入C语言的世界吧 实现一个函数&#xff0c;可以左旋字符串中的k个字符。 例如&#xff1a; A…...

有趣且重要的JS知识合集(18)浏览器实现前端录音功能

1、主题描述 兼容多个浏览器下的前端录音功能&#xff0c;实现六大录音功能&#xff1a; 1、开始录音 2、暂停录音 3、继续录音 4、结束录音 5、播放录音 6、上传录音 2、示例功能 初始状态&#xff1a; 开始录音&#xff1a; 结束录音&#xff1a; 录音流程 &#xf…...

除了Cesium和Mapbox,用three-tile+Three.js打造轻量级WebGIS的完整实践

用three-tileThree.js构建轻量级WebGIS的工程实践指南 在Web三维地图开发领域&#xff0c;Cesium和Mapbox长期占据主导地位&#xff0c;但它们"全家桶"式的架构往往成为灵活定制的桎梏。当项目需要精细控制渲染管线、深度集成业务逻辑或追求极致性能时&#xff0c;开…...

不止于步骤:用SPM预处理fMRI数据时,那些没人告诉你的‘隐藏’技巧与效率工具

不止于步骤&#xff1a;用SPM预处理fMRI数据时&#xff0c;那些没人告诉你的‘隐藏’技巧与效率工具 当你面对上百个被试的fMRI数据时&#xff0c;是否曾为重复点击SPM的GUI界面而感到疲惫&#xff1f;是否担心手动操作带来的潜在错误&#xff1f;本文将带你超越基础教程&#…...

【NR 定位】3GPP NR Positioning 5G定位标准解读(七):RRC_INACTIVE状态下的高效定位机制

1. RRC_INACTIVE状态下的5G定位挑战与机遇 在5G网络中&#xff0c;RRC_INACTIVE状态是一种独特的节能模式&#xff0c;它允许设备在保持部分网络连接的同时大幅降低功耗。这种状态特别适合物联网设备&#xff0c;比如智能电表、资产追踪器和可穿戴设备。想象一下你家的智能门锁…...

pdf2htmlEX高级调试技术:汇编级调试与反汇编

pdf2htmlEX高级调试技术&#xff1a;汇编级调试与反汇编 【免费下载链接】pdf2htmlEX Convert PDF to HTML without losing text or format. 项目地址: https://gitcode.com/gh_mirrors/pd/pdf2htmlEX pdf2htmlEX是一款能够将PDF文件转换为HTML格式同时保持文本和格式完…...

英雄联盟游戏助手:5大功能全面解析,打造你的专属游戏体验

英雄联盟游戏助手&#xff1a;5大功能全面解析&#xff0c;打造你的专属游戏体验 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit …...

告别龟速下载!手把手教你用Aspera ascp命令高效获取SRA数据(附常见错误排查)

告别龟速下载&#xff01;手把手教你用Aspera ascp命令高效获取SRA数据&#xff08;附常见错误排查&#xff09; 在生物信息学研究中&#xff0c;获取公共数据库中的测序数据是许多分析的第一步。然而&#xff0c;传统的FTP下载方式往往速度缓慢&#xff0c;尤其是当需要下载大…...

vue-sonner:轻量级Vue通知组件的高效集成方案

vue-sonner&#xff1a;轻量级Vue通知组件的高效集成方案 【免费下载链接】vue-sonner &#x1f514; An opinionated toast component for Vue. 项目地址: https://gitcode.com/gh_mirrors/vu/vue-sonner 项目概述 vue-sonner是一个为Vue和Nuxt应用设计的轻量级通知组…...

如何快速掌握KLayout:专业版图设计的终极实战指南

如何快速掌握KLayout&#xff1a;专业版图设计的终极实战指南 【免费下载链接】klayout KLayout Main Sources 项目地址: https://gitcode.com/gh_mirrors/kl/klayout KLayout是一款功能强大的开源版图设计工具&#xff0c;专门用于集成电路&#xff08;IC&#xff09;和…...

告别文档迁移困境:3个关键场景解锁飞书文档批量备份新方案

告别文档迁移困境&#xff1a;3个关键场景解锁飞书文档批量备份新方案 【免费下载链接】feishu-doc-export 项目地址: https://gitcode.com/gh_mirrors/fe/feishu-doc-export 还在为团队协作平台切换带来的文档迁移难题而烦恼吗&#xff1f;当企业从飞书切换到其他办公…...

3步掌握DoL-Lyra整合包:从零到精通的完整指南

3步掌握DoL-Lyra整合包&#xff1a;从零到精通的完整指南 【免费下载链接】DOL-CHS-MODS Degrees of Lewdity 整合 项目地址: https://gitcode.com/gh_mirrors/do/DOL-CHS-MODS Degrees of Lewdity中文整合包DoL-Lyra为您提供了一站式的游戏体验解决方案。这个自动化构建…...