当前位置: 首页 > 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…...

别再死记硬背了!一张图+一个故事,帮你彻底搞懂分治、动态规划和贪心法的区别

算法三剑客&#xff1a;用旅行规划故事理解分治、动态规划与贪心法 想象你正在计划一次横跨欧亚大陆的三个月背包旅行。面对错综复杂的路线选择、预算分配和景点取舍&#xff0c;不同的决策策略会带来截然不同的旅行体验——这恰恰是分治法、动态规划和贪心算法在现实中的生动映…...

2026论文写作工具红黑榜:AI论文网站怎么选?这份榜单够用!

红榜优先选千笔AI、ThouPen、豆包&#xff0c;适配国内学术规范&#xff1b;黑榜避开低质免费工具、无真实引用平台、过度依赖全文生成的工具&#xff0c;优先按需求匹配三维模型&#xff08;需求匹配度 - 数据可信度 - 成本承受力&#xff09;。 一、红榜&#xff1a;10 款高分…...

国光黑苹果安装完整指南:OpenCore配置终极教程

国光黑苹果安装完整指南&#xff1a;OpenCore配置终极教程 【免费下载链接】Hackintosh 国光的黑苹果安装教程&#xff1a;手把手教你配置 OpenCore 项目地址: https://gitcode.com/gh_mirrors/hac/Hackintosh 你是否渴望在普通PC上体验macOS的流畅与优雅&#xff0c;但…...

如何让经典GTA游戏重获新生:终极SilentPatch修复工具完全指南

如何让经典GTA游戏重获新生&#xff1a;终极SilentPatch修复工具完全指南 【免费下载链接】SilentPatch SilentPatch for GTA III, Vice City, and San Andreas 项目地址: https://gitcode.com/gh_mirrors/si/SilentPatch 你是否还记得那些在GTA III、Vice City和San An…...

经典游戏无法运行?DDrawCompat让老游戏在新系统重生

经典游戏无法运行&#xff1f;DDrawCompat让老游戏在新系统重生 【免费下载链接】DDrawCompat DirectDraw and Direct3D 1-7 compatibility, performance and visual enhancements for Windows Vista, 7, 8, 10 and 11 项目地址: https://gitcode.com/gh_mirrors/dd/DDrawCom…...

Ansys SCDM高效建模技巧:从基础到进阶

1. 初识Ansys SCDM&#xff1a;工程师的3D建模利器 第一次打开Ansys SpaceClaim Direct Modeler&#xff08;简称SCDM&#xff09;时&#xff0c;你可能会有种相见恨晚的感觉。这个被工程师们称为"几何手术刀"的软件&#xff0c;用起来比传统CAD软件顺手得多。我当年…...

Claude Code安装保姆级教程!超简单上手就会!

Claude Code驾驶手册 文章目录 Claude Code驾驶手册0 前言1 Claude Code基本安装配置1.1 系统配置及安装1.2 启动Claude Code1.3 配置API 0 前言 AI Agent 称为智能体&#xff08;或人工智能代理&#xff09;&#xff0c;本质是自动执行任务的程序&#xff0c;核心在于让模型不…...

终极指南:5步解决魔兽争霸III在现代Windows系统上的兼容性问题

终极指南&#xff1a;5步解决魔兽争霸III在现代Windows系统上的兼容性问题 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 还在为魔兽争霸III在Window…...

OpenClaw调试技巧:GLM-4.7-Flash任务执行日志分析与问题定位

OpenClaw调试技巧&#xff1a;GLM-4.7-Flash任务执行日志分析与问题定位 1. 为什么需要关注OpenClaw的调试日志 上周我在尝试用OpenClaw自动整理项目文档时&#xff0c;遇到了一个奇怪的现象&#xff1a;任务明明显示执行成功&#xff0c;但最终生成的Markdown文件却缺失了关…...

像素幻梦部署实战:阿里云ECS+GPU实例零配置运行像素工坊全记录

像素幻梦部署实战&#xff1a;阿里云ECSGPU实例零配置运行像素工坊全记录 1. 像素幻梦创意工坊简介 像素幻梦(Pixel Dream Workshop)是一款基于FLUX.1-dev扩散模型的下一代像素艺术生成工具。它采用独特的16-bit像素工坊视觉设计&#xff0c;为创作者提供沉浸式的AI绘图体验。…...