当前位置: 首页 > news >正文

LeetCode--HOT100题(32)

目录

  • 题目描述:138. 复制带随机指针的链表(中等)
    • 题目接口
    • 解题思路
    • 代码
  • PS:

题目描述:138. 复制带随机指针的链表(中等)

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如,如果原链表中有 XY 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 xy ,同样有 x.random --> y

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0n-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)

目录 题目描述&#xff1a;138. 复制带随机指针的链表&#xff08;中等&#xff09;题目接口解题思路代码 PS: 题目描述&#xff1a;138. 复制带随机指针的链表&#xff08;中等&#xff09; 给你一个长度为 n 的链表&#xff0c;每个节点包含一个额外增加的随机指针 random &…...

SAP MM学习笔记24-以评估收货(评价)和非评估收货(非评价)

SAP 中 有评价入库&#xff08;评估收货&#xff09;和非评价入库&#xff08;非评估收货&#xff09;两种入库方式。 一般来说在库品目会采用评价入库&#xff0c;而消费品目&#xff0c;会采用非评价入库。 其实评价入库&#xff0c;非评价入库对外都无所谓的&#xff0c;人…...

Hadoop的DataNode无法启动的解决方案

Hadoop重启一次&#xff0c;里面的数据需要重新导入&#xff0c;发现无法导入数据&#xff0c;查看jps发现是DataNode没有启动&#xff0c;重新启动发现也无法启动&#xff0c;原因是前面重新启动NameNode&#xff0c;里面的文件格式化一次&#xff0c;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数据库&#xff0c;在个人电脑上运行没问题&#xff0c;别人运行时提示“提示找不到请求的 .Net Framework Data Provider。可能没有安装”。经过查询&#xff0c;安装Connector/NET 8.1.0&#xff0c;下载地址如下所示&#xff1a; https://d…...

销售自动化管理软件是什么,销售自动化管理软件有什么优势

阅读本文您可以了解&#xff1a;1、销售自动化管理软件是什么&#xff1b;2、销售自动化管理软件的优势 一、销售自动化管理软件是什么 销售自动化管理软件是一种用于帮助企业有效管理销售流程和客户关系的工具。它集成了各种功能和工具&#xff0c;以简化和自动化销售团队的任…...

MySQL 函数

mysql 函数语法 create function 函数名&#xff08;参数名 参数类型&#xff0c;。。。&#xff09; returns type —返回值类型 ----returns 有个 s [characteristics…] begin 函数体 ### 函数体中肯定有 return 语句 end 参数列表 指定参数为 IN | out | INOUT 只对存储过程…...

爬虫逆向实战(六)--猿人学第四题

一、数据接口分析 主页地址&#xff1a;猿人学第四题 1、抓包 通过抓包可以发现数据接口是api/match/4 2、判断是否有加密参数 请求参数是否加密&#xff1f; 无请求头是否加密&#xff1f; 无响应是否加密&#xff1f; 响应数据无加密&#xff0c;但是返回的却是html代码…...

【大数据Hive】hive 事务表使用详解

目录 一、前言 二、Hive事务背景知识 hive事务实现原理 hive事务原理之 —— delta文件夹命名格式 _orc_acid_version 说明 bucket_00000 合并器(Compactor) 二、Hive事务使用限制 参数设置 客户端参数设置 客户端参数设置 三、Hive事务使用操作演示 操作步骤 客…...

网络层协议

网络层协议 IP协议基本概念协议头格式网段划分特殊的IP地址IP地址的数量限制私有IP地址和公网IP地址路由IP协议头格式后续 在复杂的网络环境中确定一个合适的路径 IP协议 承接上文&#xff0c;TCP协议并不会直接将数据传递给对方&#xff0c;而是交付给下一层协议&#xff0c;…...

JWT(JSON Web Token )令牌

1、介绍 jwt就是将原始的json数据格式进行了安全的封装&#xff0c;这样就可以直接基于jwt在通信双方安全的进行信息传输了。 2、jwt组成 第一部分&#xff1a;Header(头&#xff09;&#xff0c; 记录令牌类型、签名算法等。 例如&#xff1a;{"alg":"HS256…...

leetcode 力扣刷题 滑动窗口 部分题解(记录)

力扣刷题 滑动窗口相关的部分题解 209. 长度最小的子数组904. 水果成篮76. 最小覆盖子串 209. 长度最小的子数组 leetcode题目链接 209.长度最小的子数组 题目内容是这样的&#xff1a;给定一个含有 n个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的…...

Intellij IDEA SBT依赖分析插件

可分析模块和传递依赖 安装完插件后&#xff0c;由于IDEA BUG&#xff0c;会出现两个分析按钮&#xff0c;一个是gradle的&#xff0c;一般是后者是新安装的sbt。 选择需要分析的模块 只需要在project/plugins.sbt中添加代码&#xff0c;启动官方分析插件addDependencyTreeP…...

MySQL中事务特性以及隔离机制

目录 一、什么是事务 二、事务特性——即ACID特性 三、事务的隔离级别 1、脏读 2、不可重复读 3、幻读 Read uncommitted&#xff1a; Read committed: Repeatable read: Serializable&#xff1a; 一、什么是事务 事务&#xff08;Transaction&#xff09;——一个最…...

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

描述 输入一个字符串&#xff0c;输出字符串中单词的倒序。 要求 构成单词的字符只有26个大写或小写英文字母。非构成单词的字符均视为单词间隔符&#xff1b;倒排后的单词间隔符以一个空格表示&#xff1b;如果原字符串中相邻单词间有多个间隔符时&#xff0c;倒排转换后也只…...

Kubernetes入门 四、Pod核心

目录 什么是PodPod与容器不同Pod如何管理多个容器Pod的管理-工作负载K8s中的资源清单创建使用Pod直接创建Pod使用 Deployment 创建Pod 环境变量重启策略镜像拉取策略访问 DNS 的策略资源限制初始化容器临时容器&#xff08;了解&#xff09; 什么是Pod Pod 是可以在 Kubernete…...

【JAVA】数组练习

⭐ 作者&#xff1a;小胡_不糊涂 &#x1f331; 作者主页&#xff1a;小胡_不糊涂的个人主页 &#x1f4c0; 收录专栏&#xff1a;浅谈Java &#x1f496; 持续更文&#xff0c;关注博主少走弯路&#xff0c;谢谢大家支持 &#x1f496; 数组练习 1. 数组转字符串2. 数组拷贝3.…...

Phi-3-Mini-128K实操手册:模型加载耗时优化技巧——分层加载与缓存机制应用

Phi-3-Mini-128K实操手册&#xff1a;模型加载耗时优化技巧——分层加载与缓存机制应用 1. 项目概述 Phi-3-Mini-128K是基于微软Phi-3-mini-128k-instruct模型开发的轻量化对话工具&#xff0c;专为本地部署和高效推理场景设计。该工具通过多项技术创新&#xff0c;显著提升了…...

C#运动控制库大比拼:HALCON vs Leadshine,哪个更适合你的项目?

C#运动控制库深度评测&#xff1a;HALCON与Leadshine的工业级对决 在工业自动化领域&#xff0c;选择合适的运动控制库往往决定着项目的成败。作为C#开发者&#xff0c;我们常面临一个关键抉择&#xff1a;是选择功能全面的HALCON&#xff0c;还是专注运动控制的Leadshine&…...

OpenClaw配置优化:提升GLM-4.7-Flash响应速度的3个技巧

OpenClaw配置优化&#xff1a;提升GLM-4.7-Flash响应速度的3个技巧 1. 为什么需要优化GLM-4.7-Flash的响应速度 上个月我在本地部署了OpenClaw对接GLM-4.7-Flash模型&#xff0c;最初的使用体验并不理想。一个简单的文件整理任务需要等待近20秒才能开始执行&#xff0c;而复杂…...

国内外优秀的源码网站,程序员必备收藏

在快节奏的开发环境中&#xff0c;高效获取优质源码已成为提升开发效率的关键。无论是快速搭建项目原型、学习优秀代码架构&#xff0c;还是寻找商业级系统解决方案&#xff0c;一个可靠的源码平台能为你节省大量时间和精力。今天&#xff0c;我将为大家分享一个近期在开发者圈…...

Java毕业设计基于springboot+vue的旧时光咖啡厅管理系统

前言 该系统旨在提高咖啡厅的运营效率和服务质量&#xff0c;通过集成订单管理、库存管理、员工管理、客户管理等多个功能模块&#xff0c;实现对咖啡厅日常运营的全面管理。同时&#xff0c;系统还提供了丰富的数据分析和报表功能&#xff0c;帮助管理者更好地了解咖啡厅的运营…...

嵌入式开发:裸机到OS的技术挑战与优化

嵌入式开发从裸机到操作系统的技术挑战分析1. 系统性能需求变化1.1 CPU运行速度要求嵌入式系统引入操作系统后&#xff0c;CPU需要承担额外的调度开销。实时控制系统通常需要1ms甚至更短的tick间隔来保证控制精度&#xff0c;这进一步增加了CPU的负担。现代32位微控制器的性能提…...

单细胞测序数据读取实战指南:从CellRanger到Seurat对象

1. 单细胞测序数据读取入门指南 第一次接触单细胞测序数据分析时&#xff0c;最让人头疼的就是数据读取环节。记得我刚入门那会儿&#xff0c;光是理解CellRanger输出的各种文件格式就花了整整一周时间。不过别担心&#xff0c;今天我就把这块硬骨头啃碎了讲给你听。 单细胞测序…...

Android日志记录终极指南:如何用Timber提升开发效率

Android日志记录终极指南&#xff1a;如何用Timber提升开发效率 【免费下载链接】timber JakeWharton/timber: 是一个 Android Log 框架&#xff0c;提供简单易用的 API&#xff0c;适合用于 Android 开发中的日志记录和调试。 项目地址: https://gitcode.com/gh_mirrors/ti/…...

IINA:macOS上最优雅的全能视频播放器终极指南

IINA&#xff1a;macOS上最优雅的全能视频播放器终极指南 【免费下载链接】iina 项目地址: https://gitcode.com/gh_mirrors/iin/iina 如果你在寻找一款既强大又美观的macOS视频播放器&#xff0c;IINA绝对是你的不二之选。这款基于mpv引擎的现代播放器&#xff0c;不仅…...

并发编程进阶:volatile、内存屏障与 CPU 缓存机制详解

知识点回顾 1. 什么是CQRS&#xff1f; CQRS是Command Query Responsibility Segregation的缩写&#xff0c;一般称作命令查询职责分离。从字面意思理解&#xff0c;就是将命令&#xff08;写入&#xff09;和查询&#xff08;读取&#xff09;的责任划分到不同的模型中。 对比…...