力扣hot100:138. 随机链表的复制(技巧,数据结构)

2024-06-06 00:36

本文主要是介绍力扣hot100:138. 随机链表的复制(技巧,数据结构),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LeetCode:138. 随机链表的复制
在这里插入图片描述
这是一个经典的数据结构题,当做数据结构来学习。

1、哈希映射

需要注意的是,指针也能够当做unordered_map的键值,指针实际上是一个地址值,在unordered_map中,使用指针的实际内存地址值计算哈希函数,通过指针值来判断两个键值是否相等。

在第一次遇到这个问题时,最容易想到的方法自然是使用哈希表直接构造一模一样的。
遇到任何一个新结点直接构造,并用哈希表存储映射,然后依次遍历连接,每个遍历到的结点仅有可能被构造过,但不可能更新过nextrandom

使用哈希表:

  • 时间复杂度: O ( n ) O(n) O(n),其中n是链表的长度
    • 依次遍历,每个节点被遍历一次,每个节点被构造一次,每个节点被插入到哈希表一次,每个节点本身以及其后继和随机指向都在哈希表中被查找一次,平均查找和插入的速度为 O ( 1 ) O(1) O(1)
  • 空间复杂度: O ( n ) O(n) O(n),哈希表的空间
    在这里插入图片描述
class Solution {
public:Node* copyRandomList(Node* head) {unordered_map<Node *,Node *> mp;for(Node * p = head; p != nullptr; p = p->next){Node * nw;if(mp.count(p) == 0) {nw = new Node(p->val);mp[p] = nw;}//不重复构造,每个遍历到的结点p都需要更新next 和 randomelse nw = mp[p];if(p->next){//是否有后继if(mp.count(p->next) == 0){//后继是否被构造过Node * nw_nex =  new Node(p->next->val); //如果没有的话,则构造并建立映射,连接后继mp[p->next] = nw_nex;nw->next = nw_nex;}else nw->next = mp[p->next];//有被构造过直接连接后继}if(p->random){if(mp.count(p->random) == 0){Node * nw_random =new Node(p->random->val);mp[p->random] = nw_random;nw->random = nw_random;}else nw->random = mp[p->random];}}return mp[head];}
};
  • 当然直接遍历一次构建所有哈希映射,然后再连接会更简单,可以减少判断是否被构造过的情况,因为先建立之后一定被构造。
    • 这种方法只需要遍历两遍链表,每个结点进行一次哈希插入,以及进行其的后继和其随机指针进行一次哈希查找即可。

2、迭代 + 节点拆分(技巧性)

在这里插入图片描述第一遍遍历:拷贝结点,并将拷贝出的结点作为原结点的后继,拷贝后的结点的后继指向原结点的原始后继;
第二遍遍历:更新random
第三遍遍历:节点拆分,将拷贝出的结点和原始节点拆出来变成俩链。

你会发现,将拷贝结点作为原结点的后继,拷贝后的结点的后继指向原结点的原始后继并不影响原链表的遍历,因此这个方法是可行的。

这个方法拷贝的思想相当于先拷贝后继,将其放入到原始节点的后继。这并不会导致无法实现原链表的任何功能。然后再更新拷贝后的结点的信息,这时更新时所有原始链表的结点都已经被拷贝过一次,所有信息都可以直接使用。而不需要像方法一一样,顺序遍历更新,并不一定能保证random已经被创建出来,因此只能用哈希表存储

  • 时间复杂度: O ( n ) O(n) O(n),n是链表长度
    • 遍历一遍链表,拆分一次链表
  • 空间复杂度: O ( 1 ) O(1) O(1)
    在这里插入图片描述
class Solution {
public:Node* copyRandomList(Node* head) {if(!head) return head;//拷贝结点,更新后继Node * cur = head;while(cur){Node * nextNode = cur->next;cur->next = new Node(cur->val);cur->next->next = nextNode;cur = nextNode;}//更新randomcur = head;while(cur){if(cur->random) cur->next->random = cur->random->next;//random可能为空cur = cur->next->next;}//节点拆分cur = head;Node * p = new Node(0);Node * result = p;while(cur){p->next = cur->next;p = p->next;cur->next = cur->next->next;cur = cur->next;}return result->next;}
};

这篇关于力扣hot100:138. 随机链表的复制(技巧,数据结构)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1034620

相关文章

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

电脑win32spl.dll文件丢失咋办? win32spl.dll丢失无法连接打印机修复技巧

《电脑win32spl.dll文件丢失咋办?win32spl.dll丢失无法连接打印机修复技巧》电脑突然提示win32spl.dll文件丢失,打印机死活连不上,今天就来给大家详细讲解一下这个问题的解... 不知道大家在使用电脑的时候是否遇到过关于win32spl.dll文件丢失的问题,win32spl.dl

电脑报错cxcore100.dll丢失怎么办? 多种免费修复缺失的cxcore100.dll文件的技巧

《电脑报错cxcore100.dll丢失怎么办?多种免费修复缺失的cxcore100.dll文件的技巧》你是否也遇到过“由于找不到cxcore100.dll,无法继续执行代码,重新安装程序可能会解... 当电脑报错“cxcore100.dll未找到”时,这通常意味着系统无法找到或加载这编程个必要的动态链接库

如何关闭 Mac 触发角功能或设置修饰键? mac电脑防止误触设置技巧

《如何关闭Mac触发角功能或设置修饰键?mac电脑防止误触设置技巧》从Windows换到iOS大半年来,触发角是我觉得值得吹爆的MacBook效率神器,成为一大说服理由,下面我们就来看看mac电... MAC 的「触发角」功能虽然提高了效率,但过于灵敏也让不少用户感到头疼。特别是在关键时刻,一不小心就可能触

通过Python脚本批量复制并规范命名视频文件

《通过Python脚本批量复制并规范命名视频文件》本文介绍了如何通过Python脚本批量复制并规范命名视频文件,实现自动补齐数字编号、保留原始文件、智能识别有效文件等功能,听过代码示例介绍的非常详细,... 目录一、问题场景:杂乱的视频文件名二、完整解决方案三、关键技术解析1. 智能路径处理2. 精准文件名

前端bug调试的方法技巧及常见错误

《前端bug调试的方法技巧及常见错误》:本文主要介绍编程中常见的报错和Bug,以及调试的重要性,调试的基本流程是通过缩小范围来定位问题,并给出了推测法、删除代码法、console调试和debugg... 目录调试基本流程调试方法排查bug的两大技巧如何看控制台报错前端常见错误取值调用报错资源引入错误解析错误

mysql线上查询之前要性能调优的技巧及示例

《mysql线上查询之前要性能调优的技巧及示例》文章介绍了查询优化的几种方法,包括使用索引、避免不必要的列和行、有效的JOIN策略、子查询和派生表的优化、查询提示和优化器提示等,这些方法可以帮助提高数... 目录避免不必要的列和行使用有效的JOIN策略使用子查询和派生表时要小心使用查询提示和优化器提示其他常

Apache伪静态(Rewrite).htaccess文件详解与配置技巧

《Apache伪静态(Rewrite).htaccess文件详解与配置技巧》Apache伪静态(Rewrite).htaccess是一个纯文本文件,它里面存放着Apache服务器配置相关的指令,主要的... 一、.htAccess的基本作用.htaccess是一个纯文本文件,它里面存放着Apache服务器

Spring中@Lazy注解的使用技巧与实例解析

《Spring中@Lazy注解的使用技巧与实例解析》@Lazy注解在Spring框架中用于延迟Bean的初始化,优化应用启动性能,它不仅适用于@Bean和@Component,还可以用于注入点,通过将... 目录一、@Lazy注解的作用(一)延迟Bean的初始化(二)与@Autowired结合使用二、实例解

linux如何复制文件夹并重命名

《linux如何复制文件夹并重命名》在Linux系统中,复制文件夹并重命名可以通过使用“cp”和“mv”命令来实现,使用“cp-r”命令可以递归复制整个文件夹及其子文件夹和文件,而使用“mv”命令可以... 目录linux复制文件夹并重命名我们需要使用“cp”命令来复制文件夹我们还可以结合使用“mv”命令总