【链表】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云服务…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
MySQL的pymysql操作
本章是MySQL的最后一章,MySQL到此完结,下一站Hadoop!!! 这章很简单,完整代码在最后,详细讲解之前python课程里面也有,感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...
【Veristand】Veristand环境安装教程-Linux RT / Windows
首先声明,此教程是针对Simulink编译模型并导入Veristand中编写的,同时需要注意的是老用户编译可能用的是Veristand Model Framework,那个是历史版本,且NI不会再维护,新版本编译支持为VeriStand Model Generation Suppo…...
WebRTC调研
WebRTC是什么,为什么,如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...
倒装芯片凸点成型工艺
UBM(Under Bump Metallization)与Bump(焊球)形成工艺流程。我们可以将整张流程图分为三大阶段来理解: 🔧 一、UBM(Under Bump Metallization)工艺流程(黄色区域ÿ…...
