138. 随机链表的复制 --力扣 --JAVA
题目
给你一个长度为
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作为传入参数。
解题思路
- 先排除特殊情况:若链表为null则直接返回null;
- 使用Map存储原始链表的节点和对应索引;
- 使用List来存储复制后链表的节点;
- while循环完成节点复制、next链接和存储;
- 从Map和List中获取首节点进行第二次遍历;
- 第二次遍历建立random链接。
代码展示
class Solution {public Node copyRandomList(Node head) {//排除特殊情况if (head == null){return null;}Node ans = new Node(head.val);//需要获取random的索引,所以用map比遍历List要便捷Map<Node, Integer> headMap = new HashMap<>();//只需要根据索引获取对应节点,List本身是有序的,所以不需要用MapList<Node> ansList = new ArrayList<>();int index = 0;headMap.put(head, index);ansList.add(ans);//遍历生成所有节点并存储起来while (head.next != null){head = head.next;ans.next = new Node(head.val);index++;headMap.put(head, index);ansList.add(ans.next);ans = ans.next;}for (Node node : headMap.keySet()){if(headMap.get(node) == 0){head = node;break;}}ans = ansList.get(0);while (head != null && ans != null){Integer num = headMap.get(head.random);Node temp = null;if(num != null){temp = ansList.get(num);}ans.random = temp;head = head.next;ans = ans.next;}return ansList.get(0);}
}
相关文章:
138. 随机链表的复制 --力扣 --JAVA
题目 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点…...
Python Flask 框架开发
1. Python 代码示例(使用 Flask 框架) 1.1 安装依赖库 pip install flask flask_sqlalchemy flask_login flask_wtf 1.2 主应用文件 app.py from flask import Flask, request, jsonify, redirect, url_for, render_template, flash from flask_sqla…...
k8s安装-学习环境
目录 环境准备 配置hosts 关闭防火墙 关闭交换分区 调整swappiness参数 关闭setlinux Ipv4转发 时钟同步 安装Docker 配置Yum源 安装 配置 启动 日志 安装k8s 配置Yum源 Master节点 安装 初始化 配置kubectl 部署CNI网络插件 Node节点 检查 环境准备 准…...
Vue3动态表单
示例代码如下: // 引入需要的依赖包 import { ref, reactive } from vue; import { useForm } from /composables/useForm;// 定义表单数据模型 const formModel reactive({name: ,age: ,gender: , });// 使用自定义的useForm函数创建表单实例 const { register, …...
2312skia,15vulkan及技巧
ANGLE介绍 ANGLE,把OpenGLES2或3调用转换为DirectX9,11或OpenGL调用.这些说明记录了如何在Windows或Linux上使用ANGLE而不是本地OpenGL后端. 细节 gclient sync下载ANGLE的源码及Skia的其他仅测试依赖项. 要针对ANGLE构建Skia测试工具,请添加skia_use_angletrue到args.gn文件…...
TLSF算法概念,原理,内存碎片问题分析
TLSF算法介绍 TLSF(Two-Level Segregated Fit,两级分割适应算法)。 第一级(first level,简称fl):将内存大小按2的幂次方划分一个粗粒度的范围,如一个72字节的空闲内存的fl是6(72介…...
sharding-jdbc实现分库分表
shigen日更文章的博客写手,擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长,分享认知,留住感动。 😅😅最近几天的状态有点不对,所以有几天没有更新了。 当我们的数据量比较大…...
JDK中lock锁的机制,其底层是一种无锁的架构实现的,公平锁和非公平锁
简述JDK中lock锁的机制,其底层是一种无锁的架构实现的,是否知道其是如何实现的 synchronized与lock lock是一个接口,而synchronized是在JVM层面实现的。synchronized释放锁有两种方式: 获取锁的线程执行完同步代码,…...
c++通过serial库进行上下位机通信
编辑 风紊 现役大学牲,半退休robomaster视觉队员 写在前面 本文章主要介绍的是如何通过开源的serial库和虚拟串口实现上位机和下位机通信。 需求 假设下位机有这样一个数据报发送给上位机 struct DataRecv {char start s;TeamColor color TeamColor::Blu…...
【傻瓜级JS-DLL-WINCC-PLC交互】7.C#直连PLC并读取PLC数据
思路 JS-DLL-WINCC-PLC之间进行交互,思路,先用Visual Studio创建一个C#的DLL控件,然后这个控件里面嵌入浏览器组件,实现JS与DLL通信,然后DLL放入到WINCC里面的图形编辑器中,实现DLL与WINCC的通信。然后PLC与…...
指针常量和常量指针的区别
文章目录 指针常量常量指针即是指针常量又是常量指针 指针常量 指针常量的本质是常量,表示的是 这个指针所指向的地址不能发生改变。即指针变量的值(即地址值)不能发生修改。但是指针所指向的那块内存里的值是可以修改的。 注意:…...
离散化算法总结
离散化是将大范围的数字映射到小范围的区间内,适用于稀疏的区间。 两个问题需要考虑: 1. 原数组中可能有重复元素,需要去重。 2. 如何算出离散化后的值(离散化后保序,使用二分)。 题目链接: …...
【海思SS528 | VO】MPP媒体处理软件V5.0 | VO模块编程总结
😁博客主页😁:🚀https://blog.csdn.net/wkd_007🚀 🤑博客内容🤑:🍭嵌入式开发、Linux、C语言、C、数据结构、音视频🍭 🤣本文内容🤣&a…...
逻辑卷管理器lvm
啥意思,个人理解就是可以将物理分区合并一起组成大的磁盘,也可以移除其中的某个分区。 有四个概念需要了解下 PV,物理卷,VG 卷用户组,PE物理扩展块,LV逻辑卷 p物理,v卷,g用户组&a…...
函数声明后的“ - >”是什么?
这种语法的优势之一是可以在函数的返回类型中使用函数参数,使得返回类型更灵活。 先来看一个使用尾返回类型的例子: #include <iostream> auto add(int a, int b) -> int {return a b; }int main() {std::cout << add(3, 4) <<…...
51爱心流水灯32灯炫酷代码
源代码摘自远眺883的文章,大佬是30个灯的,感兴趣的铁汁们可以去看看哦~(已取得原作者的许可):基于STC89C51单片机设计的心形流水灯软件代码部分_单片机流水灯代码_远眺883的博客-CSDN博客 由于博主是个小菜鸡ÿ…...
将不同时间点的登录状态记录转化为不同时间段的相同登录状态SQL求解
题目 有不同时间点的登录状态记录表state_log如下 请使用sql将其转化为如下表的不同时间段的相同登录状态记录 思路分析: 此类问题需要用到lag或lead函数取上下行对应的数据,然后对前后结果做比较打标签(0或1),再…...
正则表达式与SQL数据库教程
使用正则表达式通过用例查询 Postgres 数据库: 正则表达式(又名 Regex) 正则表达式是一个强大的工具,广泛用于模式匹配和文本操作。 几乎所有编程语言都支持它们,并且经常用于文本提取、搜索和匹配文本等用例。 正则…...
HTML_web扩展标签
1.表格标签 2.增强表头表现 4.表格属性(实际不常用) 结构标签: 合并单元格: 更多请查看主页...
论文阅读:Distributed Initialization for VVIRO with Position-Unknown UWB Network
前言 Distributed Initialization for Visual-Inertial-Ranging Odometry with Position-Unknown UWB Network这篇论文是发表在ICRA 2023上的一篇文章,本文提出了一种基于位置未知UWB网络的一致性视觉惯性紧耦合优化测距算法( DC-VIRO )的分布式初始化方法。 对于…...
业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
