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----《图神经网络入门》 图神经网络信息传递积累 图在我们身边随处可见,现实世界中的物体通常是根据它们与其他事物的联系来定义的。一组物体以及它们之间的联系可以很自然地用图来表示。十多年来,研究人…...

详解[ZJCTF 2019]NiZhuanSiWei 1(PHP两种伪协议、PHP反序列化漏洞、PHP强比较)还有那道题有这么经典?
题目环境: <?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的作用:将生成的目标、文件复制到指定的安装目录中,可以是可执行文件、库文件、 配置文件等 若有一个c可执行文件,可以使用install将其安装到标准的可执行路径中,以便于直接运行,而无需指定完整的文…...

11-13 /11-14代理模式 AOP
调用者 代理对象 目标对象 代理对象除了可以完成核心任务,还可以增强其他任务,无感的增强 代理模式目的: 不改变目标对象的目标方法的前提,去增强目标方法 分为:静态代理,动态代理 静态代理 有对象->前提需要有一个类,那么我们可以事先写好一个类&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进阶知识
🙈作者简介:练习时长两年半的Java up主 🙉个人主页:程序员老茶 🙊 ps:点赞👍是免费的,却可以让写博客的作者开心好久好久😎 📚系列专栏:Java全栈,…...
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:如何把后端传过来的数组的其中一个对象加入新的属性
加入我们是更改数组中的第一个对象,在vue中可以使用$set方法将属性插入到第一个对象中作为属性。 Script部分: <script>export default {data() {return {boxes: [//模拟后端传过来的数组{id:1,name:张三},{id:2,name:李四},{id:3,name:王五},{i…...

数据库数据恢复—MSSQL报错“附加数据库错误823”如何恢复数据?
数据库故障&分析: MSSQL Server数据库比较常见的报错是“附加数据库错误823”。如果数据库有备份,只需要还原备份即可;如果无备份或者备份不可用,则需要使用专业的数据恢复手段去恢复数据。 MSSQL Server数据库出现“823”的报…...
如何使用 Java 设计一个简单的成绩计算程序
简介 本文将介绍如何使用 Java 设计一个简单的成绩计算程序。该程序可以读取学生的成绩并计算出平均分、最高分和最低分等。通过这个例子,我们将展示如何使用面向对象的思想和一些常用的 Java 功能来解决实际问题。 需求分析 在开始编写程序之前,我们…...
requests 在 Python 3.2 中使用 OAuth 导入失败的问题与解决方案
问题背景 在Python 3.2中,尝试使用Request的OAuth支持时,遇到了OAuth导入失败的问题。以下代码:import requests from requests.auth import OAuth1url https://api.twitter.com/1/account/settings.jsonqueryoauth OAuth1(client_key, cli…...

山东省技能兴鲁网络安全大赛 web方向
文章目录 购买FLAG日志里的FLAG一只小蜜蜂 购买FLAG 随便登录admin进去,发现有充值和购买功能 但是试试充值发现不行 购买页面如下 bp抓包看看,发现value值可控 我们试试将其改为正数,发现成功 购买得到flag 日志里的FLAG <?phphi…...

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

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

MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具
第2章 虚拟机性能监控,故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令:jps [options] [hostid] 功能:本地虚拟机进程显示进程ID(与ps相同),可同时显示主类&#x…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...

网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...

基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...