当前位置: 首页 > 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技术遇到的各种错误的…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

2025.6.9总结(利与弊)

凡事都有两面性。在大厂上班也不例外。今天找开发定位问题&#xff0c;从一个接口人不断溯源到另一个 接口人。有时候&#xff0c;不知道是谁的责任填。将工作内容分的很细&#xff0c;每个人负责其中的一小块。我清楚的意识到&#xff0c;自己就是个可以随时替换的螺丝钉&…...

【QT控件】显示类控件

目录 一、Label 二、LCD Number 三、ProgressBar 四、Calendar Widget QT专栏&#xff1a;QT_uyeonashi的博客-CSDN博客 一、Label QLabel 可以用来显示文本和图片. 核心属性如下 代码示例: 显示不同格式的文本 1) 在界面上创建三个 QLabel 尺寸放大一些. objectName 分别…...