【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发行版的名…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
C#学习第29天:表达式树(Expression Trees)
目录 什么是表达式树? 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持: 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...
sshd代码修改banner
sshd服务连接之后会收到字符串: SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢? 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头,…...
结构化文件管理实战:实现目录自动创建与归类
手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题,进而引发后续程序异常。使用工具进行标准化操作,能有效降低出错概率。 需要快速整理大量文件的技术用户而言,这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB,…...
shell脚本质数判断
shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数)shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数) 思路: 1:1 2:1 2 3:1 2 3 4:1 2 3 4 5:1 2 3 4 5-------> 3:2 4:2 3 5:2 3…...
【题解-洛谷】P10480 可达性统计
题目:P10480 可达性统计 题目描述 给定一张 N N N 个点 M M M 条边的有向无环图,分别统计从每个点出发能够到达的点的数量。 输入格式 第一行两个整数 N , M N,M N,M,接下来 M M M 行每行两个整数 x , y x,y x,y,表示从 …...
