【leetcode】138.复制带随机指针的链表



方法一:暴力求解
1️⃣遍历原链表,复制节点尾插
2️⃣更新random,原链表中的random对应第几个节点则复制链表中的random就对应第几个
📖Note
不能通过节点中的val判断random的指向,因为链表中可能存在两个val相等的节点
//创建节点
struct Node* BuyNode(int x)
{struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));newnode->val = x;newnode->next = NULL;return newnode;
}//找到random对应的节点是第几个
int FindRandom(struct Node* head, struct Node* random)
{int count = 1;while (head){if (head == random){return count;}else {count++;head = head->next;}}return count;
}struct Node* copyRandomList(struct Node* head) {struct Node* guard = (struct Node*)malloc(sizeof(struct Node));guard->next = NULL;struct Node* tail = guard;struct Node* cur = head;//复制原链表while (cur){struct Node* newnode = BuyNode(cur->val);tail->next = newnode;tail = tail->next;cur = cur->next;}//tail和cur都指向新链表的头tail = guard->next;struct Node* tmp = head;//更新randomwhile (tail){//在原链表这种判断random指向的节点是第几个int count = FindRandom(head, tmp->random);tmp = tmp->next;//更新复制链表中的randomcur = guard->next;while (count--){tail->random = cur;if (cur){cur = cur->next;}}tail = tail->next;}struct Node* newhead = guard->next;free(guard);return newhead;}
方法二:
1️⃣拷贝原节点,并链接在原节点之后
2️⃣更新拷贝节点中的random
拷贝节点中的random指向的是原节点中random指向节点的下一个节点
3️⃣将拷贝的节点解下来构成新的复制链表
struct Node* copyRandomList(struct Node* head) {struct Node* cur = head;struct Node* copy = NULL;//拷贝原节点,并链接在原节点之后while (cur){copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;cur->next = copy;cur = cur->next->next;}//更新拷贝节点的randomcur = head;while (cur){copy = cur->next;if (cur->random){copy->random = cur->random->next;}else{copy->random = NULL;}cur = cur->next->next;}//将所有拷贝节点解下来构成新链表并恢复原链表结构cur = head;struct Node* copyhead, *copytail;copyhead = copytail = NULL;while (cur){copy = cur->next;//取节点尾插if (copytail == NULL){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copytail->next;}//恢复原链表cur->next = copy->next;cur = copy->next;}return copyhead;
}
相关文章:
【leetcode】138.复制带随机指针的链表
方法一:暴力求解 1️⃣遍历原链表,复制节点尾插 2️⃣更新random,原链表中的random对应第几个节点则复制链表中的random就对应第几个 📖Note 不能通过节点中的val判断random的指向,因为链表中可能存在两个val相等的节点…...
svn工具使用
svn 介绍 解决之道: SCM:软件配置管理 所谓的软件配置管理实际就是对软件源代码进行控制与管理 CVS:元老级产品 VSS:入门级产品 ClearCase:IBM 公司提供技术支持 SVN:主流产品 什么是SVNÿ…...
SpringBoot项目使用MyBatisX+Apifox IDEA 插件快速开发
今天跟大家介绍两个快速开发项目的插件。能大大提高开发效率。希望能帮助到大家。 1、MyBatisX 插件 MyBatis-Plus为我们提供了强大的mapper和service模板,能够大大的提高开发效率。但是在真正开发过程中,MyBatis-Plus并不能为我们解决所有问题…...
Redis数据结构
Redis 支持的数据结构的列表 1、String:字符串,是 Redis 最基本的数据类型,可以存储字符串、整数和浮点数。 2、Hash:哈希表,由多个键值对组成,可以储存多个字段和值。 3、List:列表,…...
解密Redis:应对面试中的缓存相关问题
文章目录 1. 缓存穿透问题及解决方案2. 缓存击穿问题及解决方案3. 缓存雪崩问题及解决方案4. Redis的数据持久化5. Redis的过期删除策略和数据淘汰策略6. Redis分布式锁和主从同步7. Redis集群方案8. Redis的数据一致性保障和高可用性方案 导语: 在面试过程中&#…...
读取application-dev.properties的中文乱码【bug】
读取application-dev.properties的中文编码【bug】 2023-7-30 22:37:46 版权 禁止其他平台发布时删除以下此话 本文首次发布于CSDN平台 作者是CSDN日星月云 博客主页是https://blog.csdn.net/qq_51625007 禁止其他平台发布时删除以上此话 bug 读取application-dev.propert…...
Linux(centos7)如何实现配置iscsi存储多路径 及DM-Multipath的配置文件概述
安装多路径软件(系统默认安装) #第一:安装多路径软件yum -y install device-mapper device-mapper-multipath#第二:在CentOS7中启用多路径模块,mpathconf命令及相关模块加载(可以使用mpathconf -h查看用法&…...
DK7 vs JDK8 vs JDK11特性和功能的对比
JDK7 vs JDK8 vs JDK11特性和功能的对比 Java Development Kit (JDK) 是 Java 程序员所使用的开发工具包,它提供了编译、调试和运行 Java 程序所需的一切。JDK 在不同的版本中引入了许多新的特性和功能,下面我们来比较 JDK7、JDK8 和 JDK11 之间的一些重…...
你觉得企业为什么需要数据分析?
数据对于企业的作用就好比,一位士兵作战需要手枪一样,仅仅只是作为一项工具,帮助我们提高取得胜利的几率或者概率。数据只是数据,不代表业务,所起的作用也是有限的,网上那些夸大数据作用的,没有…...
SVN学习
SVN学习 以下总结是看了一个b站up主的视频总结出来的。 1. 简介 SVN是代码版本管理工具,它能记住每次的修改、查看所有修改记录、恢复到任何历史版本和恢复已经删除的文件。 SVN比起Git的好处就是使用简单,上手快;具备目录级权限控制&…...
vim怎么使用,vim使用教程,vimtutor怎么切换中文 汉化
vim 使用 在安装了 vim 的 unix 系统下可以使用 vimtutor zh_cn 开启下面的教程 序言 欢 迎 阅 读 《 V I M 教 程 》 —— 版本 1.7 Vim 是一个具有很多命令的功能非常强大的编辑器。限于篇幅,在本教程当中就不详细介绍了。本教程的…...
[golang gin框架] 43.Gin商城项目-微服务实战之后台Rbac微服务之管理员的增删改查以及管理员和角色关联
上一节讲解了后台Rbac微服务角色增删改查微服务,这里讲解权限管理Rbac微服务管理员的增删改查微服务以及管理员和角色关联微服务功能 一.实现后台权限管理Rbac之管理员增删改查微服务服务端功能 1.创建Manager模型 要实现管理员的增删改查,就需要创建对应的模型,故在server/r…...
2023-07-31力扣每日一题
链接: 143. 重排链表 题意: 将链表L0 → L1 → … → Ln - 1 → Ln变成L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … 解: 线性表法还是好写的 这边搞一下翻转法,快慢指针求翻转点(翻转后面一半然后双指针合并…...
接口自动化报告,生成本地服务并自动打开时失败
错误原因: 端口号被占用 首先可以在cmd中调出命令窗口然后执行命令netstat -ano就可以查看所有活动的链接,找到被占用的端口号 1、通过命令taskkill /f /t /im "进程名称" ,根据进程的名称杀掉所有的进程。或者taskkill /f /t /p…...
Git 的基本概念和使用方式
Git 是一种分布式版本控制系统,它能够记录文件内容的变化,并且允许用户在这些变化之间轻松地进行切换。 Git 的基本概念如下: 1. 仓库(Repository):Git 存放项目代码的地方。通常,一个仓库对应一…...
【JVM】(三) 深入理解JVM垃圾回收机制(GC)
文章目录 前言一、死亡对象的判断方法1.1 引用计数算法1.2 可达性分析算法 二、垃圾回收算法2.1 标记-清除算法2.2 复制算法2.3 标记-整理算法2.5 分代算法2.6 Minor GC 和 Major GC 前言 JVM 的垃圾回收机制(Garbage Collection)是 Java 中的重要特性之…...
Flink CEP(二) 运行源码解析
通过DemoApp学习一下,CEP的源码执行逻辑。为下一篇实现CEP动态Pattern奠定理论基础。 1. Pattern的定义 Pattern<Tuple3<String, Long, String>,?> pattern Pattern.<Tuple3<String, Long, String>>begin("begin").where(new…...
剑指Offer-学习计划(四)双指针(下)
剑指 Offer 57. 和为s的两个数字 剑指 Offer 58 - I. 翻转单词顺序 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 题目一:调整数组顺序使奇数位于偶数前面 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的…...
深度学习——常见注意力机制
1.SENet SENet属于通道注意力机制。2017年提出,是imageNet最后的冠军 SENet采用的方法是对于特征层赋予权值。 重点在于如何赋权 1.将输入信息的所有通道平均池化。 2.平均池化后进行两次全连接,第一次全连接链接的神经元较少,第二次全连…...
Python 进阶(七):高级文件操作(shutil 模块)
❤️ 博客主页:水滴技术 🌸 订阅专栏:Python 入门核心技术 🚀 支持水滴:点赞👍 收藏⭐ 留言💬 文章目录 1. 简介2. 常用函数2.1 复制文件2.2 复制目录2.3 移动文件或目录2.4 删除文件或目录2.…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例
目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码:冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...
02-性能方案设计
需求分析与测试设计 根据具体的性能测试需求,确定测试类型,以及压测的模块(web/mysql/redis/系统整体)前期要与相关人员充分沟通,初步确定压测方案及具体的性能指标QA完成性能测试设计后,需产出测试方案文档发送邮件到项目组&…...
window 显示驱动开发-如何查询视频处理功能(三)
D3DDDICAPS_GETPROCAMPRANGE请求类型 UMD 返回指向 DXVADDI_VALUERANGE 结构的指针,该结构包含特定视频流上特定 ProcAmp 控件属性允许的值范围。 Direct3D 运行时在D3DDDIARG_GETCAPS的 pInfo 成员指向的变量中为特定视频流的 ProcAmp 控件属性指定DXVADDI_QUER…...
