力扣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

相关文章

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

Java Optional的使用技巧与最佳实践

《JavaOptional的使用技巧与最佳实践》在Java中,Optional是用于优雅处理null的容器类,其核心目标是显式提醒开发者处理空值场景,避免NullPointerExce... 目录一、Optional 的核心用途二、使用技巧与最佳实践三、常见误区与反模式四、替代方案与扩展五、总结在 Java

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

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. 精准文件名