leetcode做题笔记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 作为传入参数。
思路一:回溯
c语言解法
struct Node* copyRandomList(struct Node* head) {struct Node* cur=head;while(cur){struct Node* next=cur->next;struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;cur->next=copy;copy->next=next;cur=next;}cur=head;while(cur){struct Node* copy=cur->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=copy->next;}cur=head;struct Node* copyhead=NULL,*copytail=NULL;while(cur){struct Node* copy=cur->next;struct Node* next=copy->next;if(copytail==NULL){copytail=copyhead=copy;}else{copytail->next=copy;copytail=copytail->next;}cur->next=next;cur=next;}return copyhead;}
分析:
本题要对一个特殊的链表进行复制,这个链表每个节点包含一个额外增加的随机指针 random,可以先将该链表每个节点记录下来,当记录的节点的指针指向空节点时原复制的节点也指向空,最后将操作完的链表用copytail连接起来,最后输出copyhead
总结:
本题考察对链表的操作,要将链表深拷贝即将链表复制下来再根据具体情况添加最后连接后返回
相关文章:
leetcode做题笔记138. 复制带随机指针的链表
给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。 构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 n…...
分布式文件系统的新兴力量:揭秘Alluxio的元数据管理机制【文末送书】
文章目录 写在前面01 分布式文件系统元数据的常见类型1.1 文件(inode)元数据1.2 数据块(block)元数据1.3 Worker元数据 02 分布式文件系统元数据的存储模式2.1 元数据存储在堆上(HEAP模式)2.2 元数据存储在…...
ArcGIS标注的各种用法和示例
标注是将描述性文本放置在地图中的要素上或要素旁的过程。 本文整理了ArcGIS中的各种标注方法、可能遇到的问题和细节,内容比较杂,想到哪写到哪。 一、正常标注某一字段值的内容 右键点击【属性】,在【标注】选项卡下勾选【标注此图层中的的要素】,在【文本字符串】栏中…...
修改ros中的控制器,便于仿真和驱动真实UR
UR机械臂学习(5-3):驱动ur机械臂实物——问题及解决_error: 鈥榰r_msgs::setpayloadrequest {aka struct ur__冰激凌啊的博客-程序员宝宝 - 程序员宝宝 (cxybb.com) 问题5 Action client not connected: scaled_pos_traj_controller/follow_j…...
网络广播模块2*30W 智能4G广播终端开发模块
SV-704UG 4G网络广播模块2*30W 智能4G广播终端开发模块 一、描述 SV-704UG网络音频模块是一款带2*30W功放输出的4G广播音频模块,采用高性能ARM处理器及专业Codec,能接收4G广播音频数据流,转换成音频模拟信号输出。带有一路line in输入&#…...
优思学院|什么是精益项目管理?
正确地使用精益思想和技术是可以减少项目中的浪费、提高客户满意度,并提高项目的利润率。 在现实世界中,项目经理的工作充满了挑战。他们不仅需要专注于产品和团队,还必须确保客户的满意度。同时,他们还必须与矩阵组织打交道&…...
【Android取证篇】华为设备跳出“允许USB调试“界面方法的不同方法
【Android取证篇】华为设备跳出"允许USB调试"界面方法的不同方法 华为设备在鸿蒙OS3系统之后,部分设备启用"允许USB调试"方式会有所变化,再次做个记录—【蘇小沐】 1.实验环境 系统版本Windows 11 专业工作站版22H2(2…...
在VSCode中移除不必要的扩展
在VSCode中移除不必要的扩展 在VSCode中安装扩展是编辑器缓慢且耗电的主要原因之一,因为添加的每个新扩展都会增加应用程序的内存和 CPU 使用率。 VSCode现在已经具备了非常多的功能,我们可以将一些重复工作的扩展移除掉。卸载这些现在可有可无的扩展将…...
算法刷题记录-树(LeetCode)
783. Minimum Distance Between BST Nodes 思路(DFS 中序遍历) 考虑中序遍历的性质即可 代码 class Solution { public:int min_diffnumeric_limits<int>::max();int prevnumeric_limits<int>::min()100000;int minDiffInBST(TreeNode* root) {inorderTraversa…...
Linux中安装MySQL_图解_2023新
1.卸载 为了避免不必要的错误发生,先将原有的文件包进行查询并卸载 // 查询 rpm -qa | grep mysql rpm -qa | grep mari// 卸载 rpm -e 文件名 --nodeps2.将安装包上传到指定文件夹中 这里采用的是Xftp 3.将安装包进行解压 tar -zxvf 文件名 -C 解压路径4.获取解压的全路…...
生产设备上的静电该如何处理?
在工厂生产车间里有很多机械设备,在生产运作过程中,难免会产生大量静电,静电会产生许多危害。 例如,1、会使电子设备故障、误操作而引起的电磁干扰。 2、电子元件或集成电路的静电击穿; 3、高压静电放电引起触电; 4、静电放电引起…...
山洪灾害预警方案(山洪预警解决方案的组成)
随着气候变化的不断加剧,山洪灾害在许多地区成为了极具威胁性的自然灾害之一。为了帮助地方政府和居民更好地预防和应对山洪灾害,我们设计了一套基于星创易联的SR600工业路由器和DTU200的山洪灾害预警方案,并成功在某地区进行了部署。 案…...
数据库 MVCC 详解
目录 1. 什么是 MVCC? 2. MVCC 的好处? 3. 快照读?当前读分别是什么?怎么理解? 3.1 快照读 3.2 当前读 4. 数据库的四种隔离级别 5. MVCC 实现原理 5.1 隐藏字段 5.2 undo log(版本链) 5.3 readView 6. re…...
process.nextTick和vue的nextTick区别
事情的起因是代码里用了nextTick,然后提交代码的时候才发现,引入的是process的,然后改成了使用vue的nextTick发现效果不生效了,然后百度查了查两者的区别: process.nextTick是nodejs自带的,而在浏览器中执…...
小程序实现一个 倒计时组件
小程序实现一个 倒计时组件 需求背景 要做一个倒计时,可能是天级别,也可能是日级别,时级别,而且每个有效订单都要用,就做成组件了 效果图 需求分析 需要一个未来的时间戳,或者在服务度直接下发一个未来…...
【四万字】网络编程接口 Socket API 解读大全
Socket 是网络协议栈暴露给编程人员的 API,相比复杂的计算机网络协议,API 对关键操作和配置数据进行了抽象,简化了程序编程。 本文讲述的 socket 内容源自 Linux man。本文主要对各 API 进行详细介绍,从而更好的理解 socket 编程。…...
无涯教程-JavaScript - ISREF函数
描述 如果指定的值是参考,则ISREF函数返回逻辑值TRUE。否则返回FALSE。 语法 ISREF (value) 争论 Argument描述Required/OptionalvalueA reference to a cell.Required Notes 您可以在执行任何操作之前使用此功能测试单元格的内容。 适用性 Excel 2007,Excel 2010,Exce…...
Android:获取MAC < 安卓系统11 <= 获取UUID
1.核心代码 主要的UseMac.java import android.annotation.SuppressLint; import android.content.Context; import android.net.ConnectivityManager; import android.net.NetworkInfo; import android.net.wifi.WifiInfo; import android.net.wifi.WifiManager; import an…...
线程的几种状态
目标: 1. 线程的几种状态的含义 2. 状态之间的切换条件 目录 新建(new)线程 可运行(Runnable)状态 运行(Running)状态 阻塞(Blocked)状态 等待(Waiting…...
kubernetes集群yaml文件与kubectl工具
k8s集群中对资源管理和资源对象编排部署都可以通过声明样式(yaml)文件来解决,也就是可以把需要对资源对象操作编辑到yaml格式文件中,我们把文件叫做资源清单文件,通过kubectl命令直接使用资源清单文件就可以实现对大量的资源对象进行编排部署…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
