【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.…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
laravel8+vue3.0+element-plus搭建方法
创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...
若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
