【链表】Leetcode 138. 随机链表的复制【中等】
随机链表的复制
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
- val:一个表示 Node.val 的整数。
- random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
解题思路
-
使用哈希表来存储原链表节点和复制链表节点的对应关系。
-
第一次遍历:创建新节点并构建原链表节点和新节点的映射关系。同时,复制节点的 val 值和 next 指针。
-
第二次遍历:根据原链表的 random 指针,为复制链表的对应节点设置 random 指针。
java实现
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}public class DeepCopyLinkedList {public Node copyRandomList(Node head) {if (head == null) {return null;}// 第一次遍历:创建新节点并构建原链表节点和新节点的映射关系Map<Node, Node> map = new HashMap<>();Node current = head;while (current != null) {map.put(current, new Node(current.val));current = current.next;}// 第二次遍历:根据原链表的 random 指针,为复制链表的对应节点设置 random 指针current = head;while (current != null) {Node copyNode = map.get(current);copyNode.next = map.get(current.next);copyNode.random = map.get(current.random);current = current.next;}return map.get(head);}public static void main(String[] args) {// 构造链表 1 -> 2 -> 3 -> 4 -> 5Node head = new Node(1);head.next = new Node(2);head.next.next = new Node(3);head.next.next.next = new Node(4);head.next.next.next.next = new Node(5);// 设置 random 指针head.random = head.next.next; // 1.random --> 3head.next.random = head.next.next.next; // 2.random --> 4head.next.next.random = head; // 3.random --> 1head.next.next.next.random = null; // 4.random --> nullhead.next.next.next.next.random = head.next; // 5.random --> 2// 调用 copyRandomList 方法进行深拷贝DeepCopyLinkedList solution = new DeepCopyLinkedList();Node copiedHead = solution.copyRandomList(head);// 打印复制链表while (copiedHead != null) {System.out.print("[" + copiedHead.val +", " + (copiedHead.random != null ? copiedHead.random.val : "null") +"] ");copiedHead = copiedHead.next;}// 输出:[1, 3] [2, 4] [3, 1] [4, null] [5, 2]}
}
时间空间复杂度
- 时间复杂度:O(n),其中 n 是链表的长度。
- 空间复杂度:O(n),需要额外的空间存储新节点
相关文章:
【链表】Leetcode 138. 随机链表的复制【中等】
随机链表的复制 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点…...
【计算机网络教程】(第六版)第2章课后习题答案
第二章 2-012-022-032-042-062-072-082-092-102-112-122-132-142-152-16 2-01 物理层要解决哪些问题?物理层的主要特点是什么? 答: 物理层要解决的主要问题: (1)物理层要尽可能地屏蔽掉物理设备和传输媒体&…...
抖音电商“达人客服”产品上线啦!超多作者邀你一起“321上客服”!
有问题别自己克服,来抖音电商找“达人客服” 当代年轻人购物,正在从机智省变成理智购。越来越多的人在达人直播间购物,看重的不止是优惠力度,还有服务保障。 为了帮助达人更好地服务用户,抖音电商上线了「达人客服」…...
华为防火墙二层墙(VAN/SVI/单臂路由)
二层墙只能做地址池形式的NAT。 交换机安全策略防火墙二层墙 路由器安全策略防火墙三层墙 交换机的光口是不能直接插线的,光模块,包括进和出 长距离:单模 短距离:多模 防火墙自身的ping流量需要单独配置...
idea使用git笔记
1.创建分支和切换分支 创建分支 切换分支 2.把新创建的分支提交到远程服务器上(注:如果没有提交的,随便找个文件修改再提交) (1)切换到要提交的分支,add (2)commit (3)push 3.在自己分支修改代码及提交到自己的远…...
智慧校园数据可视化有什么好处?怎么推进数字化校园方案?
在当今数字化时代,越来越多学校开始实施智慧校园计划,旨在为学生和教师提供更高效、便捷的学习和教学环境。智慧校园运用互联网、大数据、人工智能等技术,对校园内各信息进行收集、整合、分析和应用,实现教学、管理、服务等多方面…...
如何利用python编写函数fn(a,n)求数列和
1 问题 编写函数fn(a,n) 求aaaaaa⋯aa⋯aa(n个a)之和,fn须返回的是数列和,输入正整数a和n的值(两个值都不超过9),并输出fn(a,n)的结果值。 2 方法 运用def 定义函数和for 循环递归方法: 先定义fn(a,n)函数;…...
django orm DateTimeField 6位小数精度问题
from django.db.backends.mysql.base import DatabaseWrapperDatabaseWrapper.data_types[DateTimeField] "datetime"意思就是重写源码里面的DateTimeField字段...
JVM(六)——内存模型与高效并发
内存模型与高效并发 一、java 内存模型 【java 内存模型】是 Java Memory Model(JMM) 简单的说,JMM 定义了一套在多线程读写共享数据时(成员变量、数组)时,对数据的可见性、有序 性、和原子性的规则和保障…...
C++:关键字(4)
在c中的关键字就是我们各个写的各种代码 这些就是关键字,这些东西是无法当参数的,比如在给变量名设置为int那就不行 这就是个错的 在写其他的参数时候,不可以使用关键词作为参数...
STM32串口收发单字节数据原理及程序实现
线路连接: 显示屏的SCA接在B11,SCL接在B10,串口的RX连接A9,TX连接A10。 程序编写: 在上一个博客中实现了串口的发送代码,这里实现串口的接收代码,在上一个代码的基础上增加程序功能。 Seiral.…...
openGauss + Datakit搭建openGauss运维平台
系统架构OS 硬件需求:2c4g [rootlocalhost ~]# cat /etc/redhat-release CentOS Linux release 7.9.2009 (Core) [rootlocalhost ~]# uname -m x86_64 [rootlocalhost ~]# hostname -I 192.168.92.32 下载地址:https://opengauss.org/zh/download/ 下载…...
【疑惑】-谷歌是如何获取数据的
搜索引擎爬虫: 谷歌的搜索引擎通过爬虫程序在互联网上爬取和收集网页信息。这些爬虫会遵循特点的算法和规则,访问内容,并且提取出关键信息 用户的搜索行为: 当用户使用谷歌搜索引擎进行搜索的时候,谷歌会收集分析用户…...
Java static和继承
static特点 Java中的static关键字允许在没有创建类的实例的情况下进行调用。以下是static关键字的主要用途和特点: 静态变量(类变量):使用static关键字声明的变量称为静态变量或类变量。这些变量属于类本身,而不是类…...
亲身体验!人工智能对话无障碍 —— BRClient 使用指南
01 概述 BRClient 这个名字来源于“Bedrock Client”的简称,寓意是为用户提供一个坚实的基础。BRClient 作为一个开源的桌面应用,为用户提供了友好的图形界面,让每个人都能够轻松访问和使用 Claude 3 的强大功能。用户可以自定义 Claude 3 的…...
【数据库管理操作】Mysql 创建学生数据库及对数据表进行修改
MySQL 创建学生成绩数据库 1.创建数据库 create database studentscore;创建完成之后,如果需要使用该数据,使用use命令 use studentscore;创建表前查看当前数据库中包含的表 show tables; 2.创建bclass表 create table bclass( class_id char(8) …...
vue2 export default写法,computed、methods的使用
<template><div><h2>{{nameAll}}</h2><h2>{{method}}</h2><h2>{{tt()}}</h2><h2>{{firstName}}</h2><h2>更新后赋值数据:{{lastName}}</h2><h2>赋值数据:{{writeValue}}</h2>…...
负氧离子监测站:创造健康生活环境
TH-FZ5在蓝天白云之下,那一座座高耸的全彩屏负氧离子监测站,如同一支支科技的绿芽,静静破土而出,为这片土地带来了新的生命力。这些现代化的设备不仅美化了环境,更是我们呼吸健康守护者,它们的存在让我们的…...
【jvm】young gc full gc
何时触发YoungGC或FullGC YoungGC的触发时常在发生,当新生代的Eden区满了之后就会触发YoungGC。 FullGC在多个情况下都会被触发: 1、发生Young GC之前进行检查,如果“老年代可用的连续内存空间” < “新生代历次Young GC后升入老年代的对象…...
2024年腾讯云服务器租用价格_轻量和CVM报价
腾讯云服务器价格表2024年最新价格,轻量2核2G3M服务器61元一年、2核2G4M服务器99元1年,三年560元、2核4G5M服务器165元一年、3年900元、轻量4核8M12M服务器646元15个月、4核16G10M配置32元1个月、8核32G配置115元1个月,345元3个月。CVM云服务…...
C++_核心编程_多态案例二-制作饮品
#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为:煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例,提供抽象制作饮品基类,提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
Rapidio门铃消息FIFO溢出机制
关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系,以下是深入解析: 门铃FIFO溢出的本质 在RapidIO系统中,门铃消息FIFO是硬件控制器内部的缓冲区,用于临时存储接收到的门铃消息(Doorbell Message)。…...
从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
企业大模型服务合规指南:深度解析备案与登记制度
伴随AI技术的爆炸式发展,尤其是大模型(LLM)在各行各业的深度应用和整合,企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者,还是积极拥抱AI转型的传统企业,在面向公众…...
《Offer来了:Java面试核心知识点精讲》大纲
文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...
