当前位置: 首页 > 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.…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...