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 开发企业级健康管理项目》、《带你从入…...
AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
