当前位置: 首页 > 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 开发企业级健康管理项目》、《带你从入…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...