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

随机链表的复制

文章目录

  • 🍉前言
  • 🍉题目
  • 🍉分析
  • 🍉思路一:暴力解法
  • 🍉思路二:很绝的办法

🍉前言

果然,力扣的简单题不一定简单,但是中等和较难的题一定很麻烦。
这道题相当综合,对于思路二,如果看完思路后能写出代码,那说明你链表掌握得相当熟练了。

🍉题目

题目链接
在这里插入图片描述
在这里插入图片描述

🍉分析

题干很长,不过总结下来就很简单的几句话:有一链表,它每个节点除了有next,还有个random指针,random指向哪里?不知道,可能是其他节点,也可能指向NULL。然后现在要你对这样一个链表进行拷贝,得到一个新链表,新链表中每个节点random的指向和原链表一模一样。

🍉思路一:暴力解法

先复制原链表,但不复制random指针,得到一个新链表。接下来要复制 random 指针,那我们得知道它指向原链表的第几个节点,假设现在要得到第一个节点 node1 的random指向哪,那就遍历链表,直到某个节点的地址和 node1->random 一样,此时该节点就是 node1 的 random,然后要记录这个节点的位置(即第几个节点),比如 node1 指向第三个节点,那你新链表第一个节点也要指向第三个节点。(这里注意不是指向原链表的第三个节点!);如果没有找到,那就说明node1->random = NULL。
既然现在已经知道第一个节点的 random 指向第三个节点,那就遍历新链表,先遍历得到第一个节点(这里因为刚好是第一个节点,所以不用遍历,但如果不是第一个,那就要遍历了),再遍历一次找到第三个节点,然后就可以将它的地址赋给random了。
在这里插入图片描述

顺便来分析一下时间复杂度,最坏的情况是所有节点的 random 都指向最后一个节点,此时原链表中每个节点要找n次才能找到random指向的节点,有n个节点,所以就是n ^ 2;而新链表也是如此,所以时间复杂度就是O(N^2)。

这个解法比较复杂,代码的话你自行尝试咯。


🍉思路二:很绝的办法

之前的难点来源于原链表和新链表之间没有建立起联系。那么我们现在不妨这样:拷贝节点放在原链表对应的节点的后面,比如拷贝的第一个节点就插在原链表第一和第二个节点之间。最终效果如下图(黄色的表示新链表插进来的节点)
在这里插入图片描述

那么这样做有啥好处呢?假设原链表第一个节点的random指向第三个节点,那么新链表第一个节点的random 不就是第三个节点的下一个节点了吗?
说白了就是把“变”的化为“不变”,原先一个节点的random不是随便指吗?这就是“变”;而我现在可以用这种固定的方式去得到新链表所有节点random指针的指向,这是“不变”。

这种解法虽然很巧妙,但是写起来也是很麻烦的,不过嘛,相较于思路一,思路二的时间复杂度是O(N),这就是一个大提升。

第一步,先创建新链表的节点,然后插入,这个操作类似指定位置之后插入。

	typedef struct Node Node;Node* cur = head;//插入新链表的节点while(cur) {Node* next = cur->next;  //放循环里面其实是为了防止next为空Node* copy = (Node*)malloc(sizeof(Node));    //copy:待插入的新节点copy->val = cur->val;copy->next = next;cur->next = copy;cur = next;}

第二步,设置插入节点的random指针,(记得先将 cur 置为head)

	cur = head;while(cur) {Node* copy = cur->next;if(cur->random == NULL) {copy->random = NULL;} else {copy->random = cur->random->next;    //这一步最关键!}cur = copy->next;}

第三步,把新节点取出来,连起来就是拷贝后的链表了,记得把原链表拼接回去

	cur = head;Node* newhead = NULL,*newtail = NULL;     //创建新链表,然后刚才的新节点进行尾插while(cur) {Node* copy = cur->next;if(newhead == NULL) {newhead = newtail = copy;} else {newtail->next = copy;newtail = newtail->next;}cur = copy->next;}return newhead;

整个函数的代码:

typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {Node* cur = head;//插入新链表的节点while(cur) {Node* next = cur->next;  //放循环里面其实是为了防止next为空Node* copy = (Node*)malloc(sizeof(Node));copy->val = cur->val;copy->next = next;cur->next = copy;cur = next;}//设置新节点的random指针//先重置cur、copycur = head;  while(cur) {Node* copy = cur->next;if(cur->random == NULL) {copy->random = NULL;} else {copy->random = cur->random->next;}cur = copy->next;}//把新节点的random处理好之后,接下来要把这些新节点与原先节点分离,恢复原链表cur = head;Node* newhead = NULL,*newtail = NULL;while(cur) {Node* copy = cur->next;if(newhead == NULL) {newhead = newtail = copy;} else {newtail->next = copy;newtail = newtail->next;}cur = copy->next;}return newhead;
}

相关文章:

随机链表的复制

文章目录 🍉前言🍉题目🍉分析🍉思路一:暴力解法🍉思路二:很绝的办法 🍉前言 果然,力扣的简单题不一定简单,但是中等和较难的题一定很麻烦。 这道题相当综合&…...

树莓派4b编译FFmpeg支持硬件编解码

ffmpeg h264_omx解码器充分发挥树莓派gpu性能 准备 树莓派4b ,64位系统 修改树莓派的启动设置文件(/boot/config.txt)进行如下的调整: gpu_mem=256 framebuffer_depth=16安装依赖 常规依赖: sudo apt update sudo apt upgrade sudo apt -y install autoconf automake …...

开启CentOS/Debian自带的TCP BBR加速

BBR 是什么我就不多做介绍了。如果系统自带内核高于4.9 则默认已包含 BBR。 操作方法: 1、使用 root 权限运行下面代码 uname -r //内核版本高于 4.9 就行。2、开启BBR echo "net.core.default_qdiscfq" >> /etc/sysctl.conf echo "net.ip…...

视频推拉流EasyDSS直播点播平台获取指定时间快照的实现方法

视频推拉流直播点播系统EasyDSS平台,可提供流畅的视频直播、点播、视频推拉流、转码、管理、分发、录像、检索、时移回看等功能,可兼容多操作系统,在直播点播领域具有广泛的场景应用。为了便于用户集成、调用与二次开发。 今天我们来介绍下在…...

CSS---关于font文本属性设置样式总结

目录 1、color属性 2、font-size属性 3、font-weight属性 4、font-family属性 5、text-align属性 6、line-height属性 7、text-indent属性 8、letter-spacing属性 9、word-spacing属性 10、word-break属性 11、white-space属性 12、text-transform 12、writing-mo…...

7、使用真机调试鸿蒙项目

此处以华为手机为例,版本为鸿蒙4.0. 一、打开手机调试功能 1、打开开发者模式 打开“设置”—“关于手机”,连续点击“软件版本”可打开开发者模式 2、开启USB调试功能 打开“设置”—“系统更新”—“开发者选项”,下拉找到“USB调试”…...

GPT实战系列-P-Tuning本地化训练ChatGLM2等LLM模型,到底做了什么?(一)

GPT实战系列-如何使用P-Tuning本地化训练ChatGLM2等LLM模型? 文章目录 GPT实战系列-如何使用P-Tuning本地化训练ChatGLM2等LLM模型?P-Tuning微调训练概述1、预训练模型或者是torch模型2、训练器的超参数3、数据预处理工具4、加载数据5、分词处理6、数据预…...

【Python】爬虫代理IP的使用+建立代理IP池

目录 前言 一、代理IP 1. 代理IP的获取 2. 代理IP的验证 3. 代理IP的使用 二、建立代理IP池 1. 代理IP池的建立 2. 动态维护代理IP池 三、完整代码 总结 前言 在进行网络爬虫开发时,我们很容易遭遇反爬虫机制的阻碍。为了规避反爬虫机制,我们…...

JS-项目实战-新增水果库存功能实现

1、fruit.js function $(name) {if (name) {//假设name是 #fruit_tblif (name.startsWith("#")) {name name.substring(1); //fruit_tblreturn document.getElementById(name);} else {return document.getElementsByName(name); //返回的是NodeList类型}} }//当…...

mysql 常见操作指令

use k_order – 查看版本 select version(); – 查看所有数据库 show databases; – 查看所有执行引擎 show engines; – 查看当前数据库 select database(); – 查看所有table show tables; – 查看默认存储引擎 SHOW VARIABLES LIKE ‘default_storage_engine’; – 系…...

Vue3 生命周期

如下是Vue3的生命周期函数图: 一、Vue2生命周期和Vue3声明周期的区别 1. Vue2 中,只要创建Vue实例对象而不需要挂载就可以实现beforeCreate 和 created 生命周期函数。 Vue3中必须要将Vue实例对象挂载完成,所有的准备工作做完,…...

rocketmq 安装dashboard1.0.0 mq消息控制台安装 rocketmq控制台安装 rocketmq-dashboard-1.0.0编译安装

1. 官网: 下载 | RocketMQ 2. dashboard安装包位置: 在连接最下面,点击download.zip即可 3. 需要安装maven, 编译命令: mvn clean install -U -Dmaven.test.skiptrue4. 启动jar: java -jar rocketmq-dashboard-1.0.0.jar &…...

常见的数据结构有哪些?

数据结构分为逻辑结构和物理结构。 逻辑结构:指数据元素之间逻辑关系的数据结构,这里的逻辑关系是指数据元素之间的前后间关系,与数据在计算机中的存储位置无关。物理结构:指数据的逻辑结构在计算机存储空间中的存放形式称为数据…...

Spring中有哪几种方法获取HttpSession对象

Spring MVC 可以直接作为Controller的参数传入: RequestMapping(value "/test", method RequestMethod.POST, produces "application/json;charsetUTF-8")ResponseBodypublic Map test(HttpSession session, String otherParam) {//TODOre…...

springboot开启Redis缓存支持

开启缓存支持,只需要继承CachingConfigurerSupport 即可。代码如下: import com.fasterxml.jackson.annotation.JsonAutoDetect; import com.fasterxml.jackson.annotation.PropertyAccessor; import com.fasterxml.jackson.databind.ObjectMapper; impo…...

2.4 矩阵的运算法则

矩阵是数字或 “元素” 的矩形阵列。当矩阵 A A A 有 m m m 行 n n n 列,则是一个 m n m\times n mn 的矩阵。如果矩阵的形状相同,则它们可以相加。矩阵也可以乘上任意常数 c c c。以下是 A B AB AB 和 2 A 2A 2A 的例子,它们都是 …...

让文字在盒子中水平居中与垂直居中

简单方法&#xff1a; 1.先用text-align: center;将文字垂直居中。 2.再用line-height: Xpx;将元素的行高设置为与父元素同样的高度。&#xff08;这里的X代表父元素的高度&#xff09; 举例&#xff1a; 对于该网页的代码如下&#xff1a; <!DOCTYPE html> <html&…...

聊一聊前端面临的安全威胁与解决对策

前端是用户在使用您的网站或Web应用程序时首先体验到的东西。如果您的Web应用程序的前端受到侵害&#xff0c;它可能会影响整个布局&#xff0c;并造成糟糕的用户体验&#xff0c;可能难以恢复。集成前端安全变得越来越重要&#xff0c;本文将指导您通过可以应用于保护您的Web应…...

【matlab学习】现代控制

文章目录 (1) SISO Modeling(2) MIMO Modeling(3) 状态空间模型(4) 状态空间模型->传递函数(5) 传递函数->状态空间模型(6) 状态空间模型变换(7) 特征值和特征向量(8) 广义特征向量(9) 状态空间模型->约旦型 (1) SISO Modeling y ( k 2 ) 5 y ( k 1 ) 6 y ( k ) …...

Debezium报错处理系列之九十九:ConnectException: Source offset ‘file‘ parameter is missing

Debezium报错处理系列之九十九:ConnectException: Source offset file parameter is missing 一、完整报错二、错误原因三、解决方法研究Debezium技术遇到的各种错误解决方法系列文章传送门: Debezium从入门到精通系列之:百篇系列文章汇总之研究Debezium技术遇到的各种错误的…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

python如何将word的doc另存为docx

将 DOCX 文件另存为 DOCX 格式&#xff08;Python 实现&#xff09; 在 Python 中&#xff0c;你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是&#xff0c;.doc 是旧的 Word 格式&#xff0c;而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...