LeetCode--HOT100题(32)
目录
- 题目描述:138. 复制带随机指针的链表(中等)
- 题目接口
- 解题思路
- 代码
- PS:
题目描述: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作为传入参数。
LeetCode做题链接:LeetCode-复制带随机指针的链表
示例 1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2:

输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]
示例 3:

输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]
提示:
0 <= n <= 1000
-104 <= Node.val <= 104
Node.random 为 null 或指向链表中的节点。
题目接口
/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {}
}
解题思路
参考题解:图解 138. 复制带随机指针的链表
主要思路:
- 1.根据遍历到的原节点创建对应的新节点,每个新创建的节点是在原节点后面
- 2.新节点的随机指针就是原节点的随机指针的next(重点)
- 3.将两个链表分开,返回新链表
代码
/*
// Definition for a Node.
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/class Solution {public Node copyRandomList(Node head) {if (head == null) {return null;}Node p = head;//第一步,在每个原节点后面创建一个新节点//1->1'->2->2'->3->3'while (p != null) {Node newNode = new Node(p.val);newNode.next = p.next;p.next = newNode;// p 指向原链表的的下一个结点,然后继续插入p = newNode.next;}p = head;//第二步,设置新节点的随机节点while (p != null) {if (p.random != null) {// 新节点的随机指针就是原节点的随机指针的nextp.next.random = p.random.next;}// 每次都跳两次p = p.next.next;}// 定义一个新的链表头结点,这个结点的next才是我们需要返回的新链表Node dummy = new Node(-1);p = head;Node cur = dummy;//第三步,将两个链表分离while (p != null) {cur.next = p.next;cur = cur.next;p.next = cur.next;p = p.next;}return dummy.next;}
}
成功!

PS:
感谢您的阅读!如果您觉得本篇文章对您有所帮助,请给予博主一个赞喔~
相关文章:
LeetCode--HOT100题(32)
目录 题目描述:138. 复制带随机指针的链表(中等)题目接口解题思路代码 PS: 题目描述:138. 复制带随机指针的链表(中等) 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random &…...
SAP MM学习笔记24-以评估收货(评价)和非评估收货(非评价)
SAP 中 有评价入库(评估收货)和非评价入库(非评估收货)两种入库方式。 一般来说在库品目会采用评价入库,而消费品目,会采用非评价入库。 其实评价入库,非评价入库对外都无所谓的,人…...
Hadoop的DataNode无法启动的解决方案
Hadoop重启一次,里面的数据需要重新导入,发现无法导入数据,查看jps发现是DataNode没有启动,重新启动发现也无法启动,原因是前面重新启动NameNode,里面的文件格式化一次,DataNode的文件不一致&am…...
re中的match和search有什么区别?
问题:请说明以下re模块中的match和search有什么区别? re.match()与re.search()的区别 re.match()只匹配字符串的开始,如果字符串开始不符合正则表达式,则匹配失败,结果返回None,而re.search()匹配整个字符串,直到找到一个匹配 re.search() re.search()扫描整个字符串并…...
《内网穿透》无需公网IP,公网SSH远程访问家中的树莓派
文章目录 前言 如何通过 SSH 连接到树莓派步骤1. 在 Raspberry Pi 上启用 SSH步骤2. 查找树莓派的 IP 地址步骤3. SSH 到你的树莓派步骤 4. 在任何地点访问家中的树莓派4.1 安装 Cpolar内网穿透4.2 cpolar进行token认证4.3 配置cpolar服务开机自启动4.4 查看映射到公网的隧道地…...
.net连接mysql,提示找不到请求的 .Net Framework Data Provider。可能没有安装
开发完成的.net程序需要连接mysql数据库,在个人电脑上运行没问题,别人运行时提示“提示找不到请求的 .Net Framework Data Provider。可能没有安装”。经过查询,安装Connector/NET 8.1.0,下载地址如下所示: https://d…...
销售自动化管理软件是什么,销售自动化管理软件有什么优势
阅读本文您可以了解:1、销售自动化管理软件是什么;2、销售自动化管理软件的优势 一、销售自动化管理软件是什么 销售自动化管理软件是一种用于帮助企业有效管理销售流程和客户关系的工具。它集成了各种功能和工具,以简化和自动化销售团队的任…...
MySQL 函数
mysql 函数语法 create function 函数名(参数名 参数类型,。。。) returns type —返回值类型 ----returns 有个 s [characteristics…] begin 函数体 ### 函数体中肯定有 return 语句 end 参数列表 指定参数为 IN | out | INOUT 只对存储过程…...
爬虫逆向实战(六)--猿人学第四题
一、数据接口分析 主页地址:猿人学第四题 1、抓包 通过抓包可以发现数据接口是api/match/4 2、判断是否有加密参数 请求参数是否加密? 无请求头是否加密? 无响应是否加密? 响应数据无加密,但是返回的却是html代码…...
【大数据Hive】hive 事务表使用详解
目录 一、前言 二、Hive事务背景知识 hive事务实现原理 hive事务原理之 —— delta文件夹命名格式 _orc_acid_version 说明 bucket_00000 合并器(Compactor) 二、Hive事务使用限制 参数设置 客户端参数设置 客户端参数设置 三、Hive事务使用操作演示 操作步骤 客…...
网络层协议
网络层协议 IP协议基本概念协议头格式网段划分特殊的IP地址IP地址的数量限制私有IP地址和公网IP地址路由IP协议头格式后续 在复杂的网络环境中确定一个合适的路径 IP协议 承接上文,TCP协议并不会直接将数据传递给对方,而是交付给下一层协议,…...
JWT(JSON Web Token )令牌
1、介绍 jwt就是将原始的json数据格式进行了安全的封装,这样就可以直接基于jwt在通信双方安全的进行信息传输了。 2、jwt组成 第一部分:Header(头), 记录令牌类型、签名算法等。 例如:{"alg":"HS256…...
leetcode 力扣刷题 滑动窗口 部分题解(记录)
力扣刷题 滑动窗口相关的部分题解 209. 长度最小的子数组904. 水果成篮76. 最小覆盖子串 209. 长度最小的子数组 leetcode题目链接 209.长度最小的子数组 题目内容是这样的:给定一个含有 n个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的…...
Intellij IDEA SBT依赖分析插件
可分析模块和传递依赖 安装完插件后,由于IDEA BUG,会出现两个分析按钮,一个是gradle的,一般是后者是新安装的sbt。 选择需要分析的模块 只需要在project/plugins.sbt中添加代码,启动官方分析插件addDependencyTreeP…...
MySQL中事务特性以及隔离机制
目录 一、什么是事务 二、事务特性——即ACID特性 三、事务的隔离级别 1、脏读 2、不可重复读 3、幻读 Read uncommitted: Read committed: Repeatable read: Serializable: 一、什么是事务 事务(Transaction)——一个最…...
Docker知识(详细笔记)
概览图 文章目录 概览图docker 知识速查1. 初识 Docker1.1 概念1.2 特点1.3 架构1.4 应用场景1.5 安装 Docker1.6 配置 Docker 镜像 2. Docker 命令2.1 Docker 进程相关命令2.2 Docker 镜像相关命令2.3 Docker 容器相关命令 3. Docker 容器的数据卷3.1 数据卷概念及作用3.1.1 概…...
【C#】获取已安装的NETFramework版本集合
代码 /// <summary>/// Windows信息/// </summary>public partial class WindowsInfo{/// <summary>/// 获取已安装的NETFramework版本集合/// </summary>/// <returns></returns>public static List<string> GetInstalledNETFramew…...
对字符串中所有单词进行倒排-C语言/Java
描述 输入一个字符串,输出字符串中单词的倒序。 要求 构成单词的字符只有26个大写或小写英文字母。非构成单词的字符均视为单词间隔符;倒排后的单词间隔符以一个空格表示;如果原字符串中相邻单词间有多个间隔符时,倒排转换后也只…...
Kubernetes入门 四、Pod核心
目录 什么是PodPod与容器不同Pod如何管理多个容器Pod的管理-工作负载K8s中的资源清单创建使用Pod直接创建Pod使用 Deployment 创建Pod 环境变量重启策略镜像拉取策略访问 DNS 的策略资源限制初始化容器临时容器(了解) 什么是Pod Pod 是可以在 Kubernete…...
【JAVA】数组练习
⭐ 作者:小胡_不糊涂 🌱 作者主页:小胡_不糊涂的个人主页 📀 收录专栏:浅谈Java 💖 持续更文,关注博主少走弯路,谢谢大家支持 💖 数组练习 1. 数组转字符串2. 数组拷贝3.…...
Bilibili视频下载终极指南:如何免费高效保存B站精彩内容
Bilibili视频下载终极指南:如何免费高效保存B站精彩内容 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader 😳 项目地址: https://gitcode.com/gh_mirrors…...
实战演练:基于Spring Boot的个人博客系统,用快马AI一键生成完整后端代码
最近在尝试搭建一个个人博客系统,正好用Spring Boot练练手。作为一个Java开发者,我发现用InsCode(快马)平台可以快速生成完整的后端代码,省去了很多重复劳动。下面分享下我的实战经验: 项目初始化 首先明确需求,博客系…...
BilibiliDown全场景应用指南:从基础下载到高级定制的完整方案
BilibiliDown全场景应用指南:从基础下载到高级定制的完整方案 【免费下载链接】BilibiliDown (GUI-多平台支持) B站 哔哩哔哩 视频下载器。支持稍后再看、收藏夹、UP主视频批量下载|Bilibili Video Downloader 😳 项目地址: https://gitcode.com/gh_mi…...
C# dynamic 关键字实战:5个真实场景教你如何优雅处理动态数据
C# dynamic 关键字实战:5个真实场景教你如何优雅处理动态数据 在C#开发中,我们常常会遇到需要处理动态数据的场景——可能是来自外部API的JSON响应、Excel表格中的不确定结构,或是与Python等动态语言交互时的数据类型转换。传统的静态类型系统…...
Qt 5.9.4 + NDK r10e + JDK 1.8:一个老项目Android移植的稳定环境搭建实录
Qt 5.9.4 NDK r10e JDK 1.8:构建Android移植的黄金环境组合 在移动开发领域,技术迭代速度令人眼花缭乱,但对于那些需要维护历史Qt项目的开发者来说,稳定往往比新潮更重要。我曾接手过一个2017年开发的工业控制软件项目ÿ…...
浦语灵笔2.5-7B应用落地:教育场景中数学题截图自动解题流程
浦语灵笔2.5-7B应用落地:教育场景中数学题截图自动解题流程 1. 项目背景与价值 作为一名长期从事AI教育应用开发的技术人,我深知数学学习中的痛点:学生遇到难题时,往往需要等待老师或同学的帮助,这个过程可能打断学习…...
InstructPix2Pix实现Web端图像编辑:前端开发实战
InstructPix2Pix实现Web端图像编辑:前端开发实战 1. 为什么要把InstructPix2Pix搬到浏览器里 你有没有遇到过这样的场景:设计师同事发来一张产品图,需要临时把背景换成纯白;电商运营急着要一组节日主题的海报,但PS操…...
Codeforces Round 1082 (Div. 2)2202
Submission #368219050 - Codeforces A. Parkour Design 思路:第一个操作第三个操作两步第二个操作,所以实际上只需要考虑y坐标的变化,然后看一下x的差值是否能整除3就可以了 B. ABAB Construction 思路:奇数长度开头一定是a或者…...
为什么你需要KKS-HF_Patch?解锁Koikatsu Sunshine完整游戏体验的终极指南
为什么你需要KKS-HF_Patch?解锁Koikatsu Sunshine完整游戏体验的终极指南 【免费下载链接】KKS-HF_Patch Automatically translate, uncensor and update Koikatsu Sunshine! 项目地址: https://gitcode.com/gh_mirrors/kk/KKS-HF_Patch 你是否曾经因为语言障…...
绵羊行为检测数据集2276张VOC+YOLO格式
绵羊行为检测数据集2276张VOCYOLO格式数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):2276 标注数量(xml文件个数):2276 标注数量…...
