【LeetCode-中等题】138. 复制带随机指针的链表
文章目录
- 题目
- 解题核心思路:找random指针指向
- 思路一:哈希
- 思路二:迭代构造新链表
- 方法一:哈希+递归
- 方法二:纯哈希
- 方法三:迭代 + 节点拆分
题目

解题核心思路:找random指针指向
这里的拷贝属于深拷贝,就是不光是拷贝值,还要拷贝其指针的引用情况。如果只是单独的单向链表,则直接可以根据next指向找到下一个结点,然后创建一个新节点复制过来,直接拷贝,但是题目中的random指针指向的节点是没有归类的,这样我们就不可能使用普通的循环来进行拷贝,因为在拷贝的时候,你只能找到next,但是random并不知道,可能拷贝的同时random都还没创建出来
思路一:哈希
此题的复制,不单单要复制本身的.val值,还要把其next和random指向给复制过来。
那么我们可以借助一个哈希表Map来记录下旧链表的映射关系,key为旧链表的节点(包含next和random指向),value为新建的新节点(val值直接copy旧链表的节点)

- 建立哈希表,key为旧链表的节点,value为新建的新节点
- 然后去循环链表的同时,根据key取出新节点,并且(依据旧节点)设置新节点的next和random
- 最后返回新链表的首节点map.get(head);

这里可以用纯哈希+while或者 哈希+递归的方法,原理都是一样的
思路二:迭代构造新链表
给每个旧链表节点后面都连上一个自己的复制节点,然后再根据老节点的random给后面的新节点附上,最后在把就新链表拆出来
-
构建新老链表结合体

-
更新新节点的random

-
拆链

方法一:哈希+递归
方法一 : 递归+哈希---->用哈希表记录旧值和新值的映射,让新值根据旧值的连接关系,构建新链表Map<Node, Node> map = new HashMap<Node, Node>();public Node copyRandomList(Node head) {if(head==null) return null;if(!map.containsKey(head)){//如果map集合不含head 则创建一份新的head进去 Node newHead = new Node(head.val);map.put(head,newHead);//key--->旧值 value--->新值 //给新值附上 next 和randomnewHead.next = copyRandomList(head.next);newHead.random = copyRandomList(head.random);}return map.get(head);}
方法二:纯哈希
方法二: 纯哈希-----> 使用hash存储原结点和克隆结点的映射关系,通过映射关系处理克隆结点的random指针public Node copyRandomList(Node head) {if(head==null) return head;// map方法,空间复杂度O(n)Node oldNode = head;// 使用hash表存储旧结点和新结点的映射Map<Node,Node> map = new HashMap<>();while(oldNode != null){Node newNode = new Node(oldNode.val);map.put(oldNode,newNode);oldNode = oldNode.next;}oldNode = head;//重置 oldNode 位置到head头结点while(oldNode != null){ //根据旧node 映射新nodemap.get(oldNode).next = map.get(oldNode.next);map.get(oldNode).random = map.get(oldNode.random);oldNode = oldNode.next;}return map.get(head);//返回头结点的映射新节点}
方法三:迭代 + 节点拆分
/ 方法三: 迭代 + 节点拆分----> 给每一个旧的链表节点去拼接一个新的到旧节点后面,然后将新结点的random指向旧节点的random指向,最后再把新的节点拆分出来
public Node copyRandomList(Node head) {if (head == null) {return null;}// for (Node node = head; node != null; node = node.next.next) {// Node nodeNew = new Node(node.val);// nodeNew.next = node.next;// node.next = nodeNew;// }// 第一次遍历,拼接新旧链表 旧1-->新1-->旧2--->新2Node node = head;while(node != null){Node nodeNew = new Node(node.val);nodeNew.next = node.next;node.next = nodeNew;node = node.next.next;}// for (Node node = head; node != null; node = node.next.next) {// Node nodeNew = node.next;// if(node.random != null) nodeNew.random = node.random.next;// else nodeNew.random = null;// }// 第二次遍历,给新结点连上旧节点的randomnode = head;// 重置node到head位置while(node != null){Node nodeNew = node.next;if(node.random != null) nodeNew.random = node.random.next; //如果旧节点的random指向null null本身没有新节点,则直接让新节点的random指向nullelse nodeNew.random = null;node = node.next.next;}Node headNew = head.next;// for (Node node = head; node != null; node = node.next) {// Node nodeNew = node.next;// node.next = node.next.next;// if(nodeNew.next != null) nodeNew.next = nodeNew.next.next;// else nodeNew.next = null;// }node = head;// 重置node到head位置// 第三次遍历,拆分新链表出来while(node != null){Node nodeNew = node.next;node.next = nodeNew.next;if(nodeNew.next != null) nodeNew.next = nodeNew.next.next;else nodeNew.next = null;//防止最后一个新链表nodeNew.next.next出现空指针node = node.next;}return headNew;}
相关文章:
【LeetCode-中等题】138. 复制带随机指针的链表
文章目录 题目解题核心思路:找random指针指向思路一:哈希思路二:迭代构造新链表 方法一:哈希递归方法二:纯哈希方法三:迭代 节点拆分 题目 解题核心思路:找random指针指向 这里的拷贝属于深拷…...
C++--动态规划背包问题(1)
1. 【模板】01背包_牛客题霸_牛客网 你有一个背包,最多能容纳的体积是V。 现在有n个物品,第i个物品的体积为vivi ,价值为wiwi。 (1)求这个背包至多能装多大价值的物品? (2)若背包恰好装满&a…...
【Android-Flutter】我的Flutter开发之旅
目录: 0、文档:1、在Windows上搭建Flutter开发环境(1)[使用中国镜像(❌详细看官方文档)](https://docs.flutter.dev/community/china)(2)[下载最新版Flutter SDK(已包含Dart)](https://docs.flu…...
【Linux】深入理解文件操作
文章目录 初次谈论文件重温C语言文件操作系统文件操作接口openwriteread 再次谈论文件文件描述符文件描述符的分配规则 重定向什么是重定向重定向的本质系统调用接口实现重定向<、>、>> 初次谈论文件 开始之前先谈论一下关于文件的一些共识性问题。 一个文件可以…...
异地使用PLSQL远程连接访问Oracle数据库【内网穿透】
文章目录 前言1. 数据库搭建2. 内网穿透2.1 安装cpolar内网穿透2.2 创建隧道映射 3. 公网远程访问4. 配置固定TCP端口地址4.1 保留一个固定的公网TCP端口地址4.2 配置固定公网TCP端口地址4.3 测试使用固定TCP端口地址远程Oracle 前言 Oracle,是甲骨文公司的一款关系…...
【方案】基于AI边缘计算的智慧工地解决方案
一、方案背景 在工程项目管理中,工程施工现场涉及面广,多种元素交叉,状况较为复杂,如人员出入、机械运行、物料运输等。特别是传统的现场管理模式依赖于管理人员的现场巡查。当发现安全风险时,需要提前报告࿰…...
华为各型号交换机开启SNMP v3
设备型号:华为S5720S-28P-LI-AC 设备软件版本:V200R011C10SPC600 调试命令: snmp-agent snmp-agent sys-info version v3 snmp-agent group v3 GroupName privacy //{GroupName}是设置一个SNMP的组名,我设置是SNMPGroup snm…...
CocosCreator3.8研究笔记(一)windows环境安装配置
一、安装Cocos 编辑器 (1)、下载Cocos Dashboard安装文件 Cocos 官方网站Cocos Dashboard下载地址 : https://www.cocos.com/creator-download9下载完成后会得到CocosDashboard-v2.0.1-win-082215.exe 安装文件,双击安装即可。 …...
【JavaWeb 专题】15个最经典的JavaWeb面试题
文章目录 HTTP长连接和短连接HTTP/1.1 与 HTTP/1.0 的区别可扩展性缓存带宽优化长连接消息传递Host 头域错误提示 AjaxAjax 的优势: JSP 和 servlet 有什么区别?定义区别 JSP 的9大内置对象及作用JSP 的 4 种作用域?session 和 cookie 有什么…...
力扣:75. 颜色分类(Python3)
题目: 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort …...
JVM 内存大对象监控和优化实践
作者:vivo 互联网服务器团队 - Liu Zhen、Ye Wenhao 服务器内存问题是影响应用程序性能和稳定性的重要因素之一,需要及时排查和优化。本文介绍了某核心服务内存问题排查与解决过程。首先在JVM与大对象优化上进行了有效的实践,其次在故障转移与…...
vue indexedDB 取指定数据库指定表 全部key用request.onsuccess
1 例子 export async function funcGetKey(dbName, tableName) {return new Promise((resolve, reject) > {// 打开指定的数据库const request indexedDB.open(dbName);request.onerror (event) > {console.error(打开数据库失败: , event.target.error);reject(event…...
Java 数据结构使用学习
Set和List的区别 Set 接口实例存储的是无序的,不重复的数据。List 接口实例存储的是有序的,可以重复的元素。 Set 检索效率低下,删除和插入效率高,插入和删除不会引起元素位置改变 <实现类有HashSet,TreeSet>。 List 和数…...
monorepo更新组件报错,提示“无法加载文件 C:\Program Files\nodejs\pnpm.ps1,因为在此系统上禁止运行脚本”
解决方法: 第一步:管理员身份运行 window.powershell, win x打开powerShell命令框,进入到对应项目路径。 第二步:执行:get-ExecutionPolicy,显示Restricted,表示状态是禁止的; 第…...
vue中html引入使用<%= BASE_URL %>变量
首先使用src相对路径引入 注意: js 文件放在public文件下 不要放在assets静态资源文件下 否则 可能会报错 GET http://192.168.0.113:8080/src/assets/js/websockets.js net::ERR_ABORTED 500 (Internal Server Error) 正确使用如下:eg // html中引…...
Android全面屏下,默认不会全屏显示,屏幕底部会留黑问题
前些天发现了一个蛮有意思的人工智能学习网站,8个字形容一下"通俗易懂,风趣幽默",感觉非常有意思,忍不住分享一下给大家。 👉点击跳转到教程 公司以前的老项目,便出现了这种情况,网上搜索了各种资料…...
5.Redis-string
string 字符串 字符串类型是 Redis 最基础的数据类型,关于字符串需要特别注意: 1.⾸先Redis中所有 key 的类型都是字符串类型,⽽且其他⼏种数据结构也都是在字符串类似基础上构建的,例如 list 和 set 的元素类型是字符串类型。 2…...
docker高级(redis集群三主三从)
1. 新建6个docker容器redis实例 docker run -d --name redis-node-1 --net host --privilegedtrue -v /redis/share/redis-node-1:/data redis:6.0.8 --cluster-enabled yes --appendonly yes --port 6381docker run -d --name redis-node-2 --net host --privilegedtrue -v /…...
linux 设置与命令基础(二)
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 目录 前言 一、系统基本操作 二、命令类型 三、命令语法 四、命令补齐 五、命令帮助 六、系统基本操作命令 总结 前言 这是本人学习Linux的第二天,今天主…...
ubuntu20.04中ros2安装rosbridge及启动方式
ros2 启动rosbridge: 要启动ROS2中的rosbridge,需要先安装ROS2的rosbridge_suite软件包。使用以下命令安装: sudo apt-get update sudo apt-get install ros-<distro>-rosbridge-suite将<distro>替换为正在使用的ROS2发行版的名…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
抽象类和接口(全)
一、抽象类 1.概念:如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象,这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法,包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中,⼀个类如果被 abs…...
