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

leetcode:138. 随机链表的复制

一、题目:

138. 随机链表的复制 - 力扣(LeetCode)

 

函数原型:

struct Node* copyRandomList(struct Node* head)

二、思路

本题是给出一个单链表,单链表的每个结点还额外有一个随机指针,随机指向其他结点,要求复制该链表。

常规情况下复制链表,只需要遍历原链表,新建和原链表相同的结点尾插到新链表即可。

但是该链表有一个随机指针,还需要找到原链表中各个结点随机指针的指向,让新链表中结点的随机指针也指向新链表中的与原链表中相同位置的结点。因此还要在新链表中找到原链表中各个结点随机指针指向的结点,算法为O(N^2),且判断是否为随机指针指向的结点只能通过结点值判断,如果链表中有多个值相同的结点,九不便于判断是否为随机指针指向的结点。

 

上述方法不易实现,此处提供一个全新的思路:

由于新建一个链表每个结点的随机指针不好复制,那么就在原链表上复制每个结点,然后再复制每个结点的随机指针。

先在原链表每个结点后复制一个相同的结点,复制完成后,再次遍历链表,就可以通过当前结点随机指针指向结点的下一个结点找到复制结点随机指针需要指向的结点。最后将每个复制的结点从原链表中拆下来,重新链接组成新的链表即可完成链表的复制。

三、代码

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {struct Node*cur=head;while(cur)//在原链表每个结点后复制一个相同的结点{struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;copy->next=cur->next;cur->next=copy;cur=cur->next->next;}cur=head;while(cur){//复制结点的随机指针指向的结点就是当前结点随机指针指向结点的下一结点if(cur->random)cur->next->random=cur->random->next;elsecur->next->random=NULL;cur=cur->next->next;}cur=head;struct Node* newhead=NULL;struct Node *tail=NULL;while(cur)//拆下复制的结点并恢复原链表,重新链接这些结点{struct Node* next=cur->next;cur->next=next->next;if(tail==NULL){newhead=tail=next;}else{tail->next=next;tail=next;}cur=cur->next;}return newhead;}

相关文章:

leetcode:138. 随机链表的复制

一、题目: 138. 随机链表的复制 - 力扣(LeetCode) 函数原型: struct Node* copyRandomList(struct Node* head) 二、思路 本题是给出一个单链表,单链表的每个结点还额外有一个随机指针,随机指向其他结点&am…...

SpringBoot 全局异常之参数校验(1)

文章目录 前言背景依赖校验类型@NotBlank、@NotNull和@NotEmpty的区别@Valid和@Validated区别异常处理方式一 @RequestParam全局异常处理(ConstraintViolationException)请求示例方式二 @RequestBody(推荐)全局异常处理(MethodArgumentNotValidException)请求示例方式三(…...

QT windows与linux之间sokcet通信中文乱码问题解决方法

QT windows与linux之间sokcet通信中文乱码问题解决方法 linux发送与接收都转码utf-8: tcpClient ->write( send_msg.toUtf8());//解决乱码,发送转码 接收: QByteArray buffer tcpClient->readAll(); if(!buffer.isEmpty()) { // ui->plain…...

Java实现DXF文件转换成PDF

代码实现 public static void dxfToPdf(){// 加载DXF文件String inputFile "input.dxf";CadImage cadImage (CadImage) Image.load(inputFile);// 设置PDF输出选项PdfOptions pdfOptions new PdfOptions();pdfOptions.setPageWidth(200);pdfOptions.setPageHeigh…...

揭秘Vue中的nextTick:异步更新队列背后的技术原理大揭秘!

🎬 江城开朗的豌豆:个人主页 🔥 个人专栏 :《 VUE 》 《 javaScript 》 📝 个人网站 :《 江城开朗的豌豆🫛 》 ⛺️ 生活的理想,就是为了理想的生活 ! 目录 ⭐ 专栏简介 📘 文章引言 一、N…...

PHP使用文件缓存实现html静态化

<?php // 动态生成的内容 $content "<html><body><h1>time:".date("Y-m-d H:i:s")."</h1></body></html>"; // 静态文件保存路径和文件名 $staticFilePath "file.html"; if(file_exists($s…...

A Gentle Introduction to Graph Neural Networks

A Gentle Introduction to Graph Neural Networks----《图神经网络入门》 图神经网络信息传递积累 图在我们身边随处可见&#xff0c;现实世界中的物体通常是根据它们与其他事物的联系来定义的。一组物体以及它们之间的联系可以很自然地用图来表示。十多年来&#xff0c;研究人…...

详解[ZJCTF 2019]NiZhuanSiWei 1(PHP两种伪协议、PHP反序列化漏洞、PHP强比较)还有那道题有这么经典?

题目环境&#xff1a; <?php $text $_GET["text"]; $file $_GET["file"]; $password $_GET["password"]; if(isset($text)&&(file_get_contents($text,r)"welcome to the zjctf")){echo "<br><h1>&…...

bazel build使用【未完】

1. install install的作用&#xff1a;将生成的目标、文件复制到指定的安装目录中&#xff0c;可以是可执行文件、库文件、 配置文件等 若有一个c可执行文件&#xff0c;可以使用install将其安装到标准的可执行路径中&#xff0c;以便于直接运行&#xff0c;而无需指定完整的文…...

11-13 /11-14代理模式 AOP

调用者 代理对象 目标对象 代理对象除了可以完成核心任务&#xff0c;还可以增强其他任务,无感的增强 代理模式目的: 不改变目标对象的目标方法的前提,去增强目标方法 分为:静态代理,动态代理 静态代理 有对象->前提需要有一个类&#xff0c;那么我们可以事先写好一个类&a…...

Ubuntu 创建并发布 Django 项目

Ubuntu 创建并发布 Django 项目 升级操作系统和软件 sudo apt updatesudo apt -y dist-upgrade 安装 python3-pip sudo apt -y install python3-pip安装 django pip install -i https://pypi.tuna.tsinghua.edu.cn/simple djangosudo apt -y install python3-django创建 dj…...

SQL Server进阶知识

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开心好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…...

TFHEpp 使用记录

TFHEpp 使用记录 使用HE3DB错误randen 使用 需要使用 编译器gcc > 10 (unicode 编码) sudo apt-get install -y build-essential g-10 apt-utils ca-certificates git cmake libgmp-dev libfftw3-devgit clone https://github.com/virtualsecureplatform/TFHEpp cd TFHEp…...

大模型的实践应用6-百度文心一言的基础模型ERNIE的详细介绍,与BERT模型的比较说明

大家好,我是微学AI,今天给大家讲一下大模型的实践应用6-百度文心一言的基础模型ERNIE的详细介绍,与BERT模型的比较说明。在大规模语料库上预先训练的BERT等神经语言表示模型可以很好地从纯文本中捕获丰富的语义模式,并通过微调的方式一致地提高各种NLP任务的性能。然而,现…...

vue:如何把后端传过来的数组的其中一个对象加入新的属性

加入我们是更改数组中的第一个对象&#xff0c;在vue中可以使用$set方法将属性插入到第一个对象中作为属性。 Script部分&#xff1a; <script>export default {data() {return {boxes: [//模拟后端传过来的数组{id:1,name:张三},{id:2,name:李四},{id:3,name:王五},{i…...

数据库数据恢复—MSSQL报错“附加数据库错误823”如何恢复数据?

数据库故障&分析&#xff1a; MSSQL Server数据库比较常见的报错是“附加数据库错误823”。如果数据库有备份&#xff0c;只需要还原备份即可&#xff1b;如果无备份或者备份不可用&#xff0c;则需要使用专业的数据恢复手段去恢复数据。 MSSQL Server数据库出现“823”的报…...

如何使用 Java 设计一个简单的成绩计算程序

简介 本文将介绍如何使用 Java 设计一个简单的成绩计算程序。该程序可以读取学生的成绩并计算出平均分、最高分和最低分等。通过这个例子&#xff0c;我们将展示如何使用面向对象的思想和一些常用的 Java 功能来解决实际问题。 需求分析 在开始编写程序之前&#xff0c;我们…...

requests 在 Python 3.2 中使用 OAuth 导入失败的问题与解决方案

问题背景 在Python 3.2中&#xff0c;尝试使用Request的OAuth支持时&#xff0c;遇到了OAuth导入失败的问题。以下代码&#xff1a;import requests from requests.auth import OAuth1url https://api.twitter.com/1/account/settings.jsonqueryoauth OAuth1(client_key, cli…...

山东省技能兴鲁网络安全大赛 web方向

文章目录 购买FLAG日志里的FLAG一只小蜜蜂 购买FLAG 随便登录admin进去&#xff0c;发现有充值和购买功能 但是试试充值发现不行 购买页面如下 bp抓包看看&#xff0c;发现value值可控 我们试试将其改为正数&#xff0c;发现成功 购买得到flag 日志里的FLAG <?phphi…...

No206.精选前端面试题,享受每天的挑战和学习

🤍 前端开发工程师(主业)、技术博主(副业)、已过CET6 🍨 阿珊和她的猫_CSDN个人主页 🕠 牛客高级专题作者、在牛客打造高质量专栏《前端面试必备》 🍚 蓝桥云课签约作者、已在蓝桥云课上架的前后端实战课程《Vue.js 和 Egg.js 开发企业级健康管理项目》、《带你从入…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...