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

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

UDP(Echoserver)

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

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

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

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

接口自动化测试:HttpRunner基础

相关文档 HttpRunner V3.x中文文档 HttpRunner 用户指南 使用HttpRunner 3.x实现接口自动化测试 HttpRunner介绍 HttpRunner 是一个开源的 API 测试工具&#xff0c;支持 HTTP(S)/HTTP2/WebSocket/RPC 等网络协议&#xff0c;涵盖接口测试、性能测试、数字体验监测等测试类型…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...