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

LeetCode 138题解 | 随机链表的复制

随机链表的复制

  • 一、题目链接
  • 二、题目
  • 三、分析
  • 四、代码

一、题目链接

138.随机链表的复制

二、题目

在这里插入图片描述

三、分析

数据结构初阶阶段,为了控制随机指针,我们将拷贝结点链接在原节点的后面解决,后面拷贝节点还得解下来链接,非常麻烦。这里我们直接让{原结点,拷贝结点}建立映射关系放到map中,控制随机指针会非常简单方便,这里体现了map在解决一些问题时的价值,完全是降维打击。

深拷贝一遍原链表,并连接。确定拷贝结点的random指针就需要原结点找到对应的拷贝结点:map< 原结点,拷贝结点>。

四、代码

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {map<Node*, Node*> nodeMap;Node* copyhead = nullptr, *copytail = nullptr;Node* cur = head;while (cur){Node* copy = new Node(cur->val);if (copytail == nullptr){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copy;}nodeMap.insert({ cur, copy });// 或者 nodeMap[cur] = copytail;cur = cur->next;}cur = head;Node* copy = copyhead;while (cur){if (cur->random == nullptr){copy->random = nullptr;}else{copy->random = nodeMap[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}
};
http://www.lryc.cn/news/583258.html

相关文章:

  • 光伏无人机3D建模:毫秒级精度设计
  • 老年人与机器人玩具的情感连接
  • 什么是 AMR 格式?简鹿音频转换器轻松批量转换 AMR 为 MP3
  • 论文阅读|汽车虚拟环绕音响系统设计与实现策略的比较研究
  • OpenCV图片操作100例:从入门到精通指南(4)
  • NLP:初识RNN模型(概念、分类、作用)
  • 继承与多态:面向对象编程的两大支柱
  • stockapi股票实时tick数据,技术指标macd,kdj,cci,日k线数据
  • 如何将FPGA设计的验证效率提升1000倍以上(3)
  • oracle ocp题库有多少道题,以及题库背诵技巧
  • JavaEE初阶第八期:解锁多线程,从 “单车道” 到 “高速公路” 的编程升级(六)
  • 软件设计师中级概念题
  • Selenium+Pytest自动化测试框架实战前言#
  • 汽车工业制造领域与数字孪生技术的关联性研究​
  • Microsoft AZ-305 Exam Question
  • 迁移Oracle SH 示例 schema 到 PostgreSQL
  • 亚马逊广告进阶指南:长尾词应如何去挖掘
  • RapidRAW RAW 图像编辑器
  • 游戏开发学习记录
  • 码云创建分支
  • 分库分表之实战-sharding-JDBC绑定表配置实战
  • 掌握PDF转CAD技巧,提升工程设计效率
  • 模型内部进行特征提取时,除了“减法”之外,还有哪些技术
  • Android ttyS2无法打开该如何配置 + ttyS0和ttyS1可以
  • BEV感知算法:自动驾驶的“上帝视角“革命
  • c语言学习_函数递归2
  • 深度学习模型在C++平台的部署
  • Spring Boot微服务中集成gRPC实践经验分享
  • 1️⃣理解大语言模型
  • 百度文心一言开源ERNIE-4.5深度测评报告:技术架构解读与性能对比