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

链表学习之复制含随机指针的链表

链表解题技巧

  • 额外的数据结构(哈希表);
  • 快慢指针;
  • 虚拟头节点;

复制含随机指针的链表

该链表节点的结构如下:

class ListRandomNode {
public:ListRandomNode() : val(0), next(nullptr), random(nullptr) {}ListRandomNode(int v, ListRandomNode *n, ListRandomNode *r) : val(v), next(n), random(r) {}
public:int val;ListRandomNode *next;ListRandomNode *random;
};

要求:时间复杂度O(N),空间复杂度O(1);

方法1:哈希表

时间复杂度O(N),空间复杂度O(N);

具体思路:

  • 遍历链表,复制每个节点并存入map,key为原节点,val为新节点;
  • 再次遍历链表,每个新节点都可以通过源节点和map找到,据此连接next和random;
    • 新节点的next就是,map[源节点]的next;
    • 新节点的random就是,map[源节点]的random;
ListRandomNode* LinkedList::copyListWithRandomByMap(ListRandomNode *head) {if (head == nullptr ) return head;std::unordered_map<ListRandomNode*, ListRandomNode*> ref;// create new nodeListRandomNode *cur = head;while (cur != nullptr) {ListRandomNode *tmp = new ListRandomNode(cur->val, nullptr, nullptr);ref[cur] = tmp;cur = cur->next;}// joint new nodecur = head;while (cur != nullptr) {ref[cur]->next = ref[cur->next];ref[cur]->random = ref[cur->random];cur = cur->next;}return ref[head];
}

方法2:next

时间复杂度O(N),空间复杂度O(1);

将每一个新节点放在原来节点的后面,并连接上下一个节点的方式,这样通过next就能够定位到新节点,通过next的next就能找到原来的下一个节点。

  • 遍历一遍链表,遍历的过程中,为每一个节点创建一个新节点,新节点连接在原来两个节点之间;
  • 再次遍历链表,为random赋值:新节点的random就是,源节点random的next;
  • 再将源节点和新节点分离出来,返回新节点头即可。
ListRandomNode* LinkedList::copyListWithRandom(ListRandomNode *head) {if (head == nullptr) return head;// create new nodeListRandomNode *cur = head;while (cur != nullptr) {ListRandomNode *cur_ = new ListRandomNode(cur->val, nullptr, nullptr);ListRandomNode *tmp = cur->next;cur->next = cur_;cur_->next = tmp;cur = tmp;}// assign random pointerscur = head;while (cur != nullptr) {cur->next->random = cur->random ? cur->random->next : nullptr;cur = cur->next->next;}// splitcur = head;ListRandomNode *new_head = head->next;ListRandomNode *cur_ = head->next;while (cur_->next != nullptr) {cur->next = cur_->next;cur = cur->next;cur_->next = cur->next;cur_ = cur_->next;}cur->next = nullptr;cur_->next = nullptr;return new_head;
}

辅助函数

根据数组生成带随机值的链表:

ListRandomNode* LinkedList::generateListWithRandom(int *arr, int len) {if (arr == nullptr || len < 1) {return nullptr;}std::vector<ListRandomNode*> vec;ListRandomNode *head = new ListRandomNode(arr[0], nullptr, nullptr);ListRandomNode *cur = head;for (int i = 1; i < len; i++) {vec.push_back(cur);cur->next = new ListRandomNode(arr[i], nullptr, nullptr);cur = cur->next;}vec.push_back(cur);for (int i = 0; i < len; i++) {vec[i]->random = vec[rand() % len];}return head;
}

打印随机链表:

void LinkedList::printListWithRandom(ListRandomNode *head) {while (head) {std::cout << head->val << "[" << head->random->val << "]" << (head->next ? "->" : " ") ;head = head->next;}std::cout << std::endl;
}

相关文章:

链表学习之复制含随机指针的链表

链表解题技巧 额外的数据结构&#xff08;哈希表&#xff09;&#xff1b;快慢指针&#xff1b;虚拟头节点&#xff1b; 复制含随机指针的链表 该链表节点的结构如下&#xff1a; class ListRandomNode { public:ListRandomNode() : val(0), next(nullptr), random(nullptr…...

【人脸检测】Yolov5Face:优秀的one-stage人脸检测算法

论文题目&#xff1a;《YOLO5Face: Why Reinventing a Face Detector》 论文地址&#xff1a;https://arxiv.org/pdf/2105.12931.pdf 代码地址&#xff1a;https://github.com/deepcam-cn/yolov5-face 1.简介 近年来&#xff0c;CNN在人脸检测方面已经得到广泛的应用。但是许多…...

【Unity3d】Unity与Android之间通信

在unity开发或者sdk开发经常遇到unity与移动端原生层之间进行通信&#xff0c;这里把它们之间通信做一个整理。 关于Unity与iOS之间通信&#xff0c;参考【Unity3d】Unity与iOS之间通信 Unity(c#)调用Android (一)、编写Java代码 实际上&#xff0c;任何已经存在的Java代码…...

Allegro如何更改DRC尺寸大小操作指导

Allegro如何更改DRC尺寸大小操作指导 在做PCB设计的时候,DRC可以辅助设计,有的时候DRC的尺寸过大会影响视觉,Allegro支持将DRC的尺寸变小或者改大 如下图,DRC尺寸过大 如何改小,具体操作如下 点击Setup选择Design Parameters...

Mongodb WT_PANIC: WiredTiger library panic

文章目录故障现象排查过程1.查看Log2.同步恢复数据故障现象 周五突然收到Mongo实例莫名奇妙挂了告警&#xff0c;一般都是RS复制集架构模式&#xff08;5节点&#xff09;&#xff0c;查看此实例角色为SECONDAR&#xff0c;挂了暂时不影响线上业务&#xff0c;但还是需要尽快修…...

【HTML】HTML 表格总结 ★★★ ( 表格标签 | 行标签 | 单元格标签 | 表格标签属性 | 表头单元格标签 | 表格标题标签 | 合并单元格 )

文章目录一、表格标签组成 ( 表格标签 | 行标签 | 单元格标签 )二、table 表格属性 ( border 属性 | align 属性 | width 属性 | height 属性 )三、表头单元格标签四、表格标题标签五、合并单元格1、合并单元格方式2、合并单元格顺序3、合并单元格流程六、合并单元格示例1、原始…...

linux013之文件和目录的权限管理

用户、组、文件目录的关系&#xff1a; 简介&#xff1a;用户和组关联&#xff0c;组合文件目录关联&#xff0c;这样就实现了用户对文件的权限管理。首先来看一下&#xff0c;一个文件或目录的权限是怎么查看的&#xff0c;ls -l&#xff0c; 如下&#xff0c;这个信息怎么看呢…...

设计模式之状态模式

什么是状态模式 状态模式是指允许一个对象在其内部状态改变时改变他的行为&#xff0c;对象看起来似乎改变了整个类。     状态模式将一个对象在不同状态下的不同行为封装在一个个状态类中&#xff0c;通过设置不同的状态对象可以让环境对象拥有不同的行为&#xff0c;而状…...

XQuery 选择 和 过滤

XML实例文档 我们将在下面的例子中继续使用这个 "books.xml" 文档&#xff08;和上面的章节所使用的 XML 文件相同&#xff09;。 在您的浏览器中查看 "books.xml" 文件。 选择和过滤元素 正如在前面的章节所看到的&#xff0c;我们使用路径表达式或 FL…...

室友打了一把王者的时间,我理清楚了grep,find,管道|,xargs的区别与联系,用的时候不知道为什么要这样用

目录 问题引入 find和grep的基本区别 xargs命令 Linux命令的标准输入 vs 命令行参数 举例总结 问题引入 在自己做项目的过程中&#xff0c;想使用linux命令统计下一个目录下html文件的数量&#xff0c;在思考应该使用grep还是find去配合wc指令统计文件数量&#xff0c;后来…...

python 刷题时常见的函数

collections.OrderedDict 1. move_to_end() move_to_end() 函数可以将指定的键值对移动到最前面或者最后面&#xff0c;即最左边或最右边 。 2. popitem() popitem()可以完成元素的删除操作&#xff0c;有一个可选参数last&#xff08;默认为True&#xff09;&#xff0c;…...

Python之列表推导式和列表排序

Python中的列表推导式&#xff0c;是小编比较喜欢的一种&#xff0c;他能大大减少你的代码量来得到你想要的结果&#xff0c;下面说说列表中常用的几种推导式 列表排序 Python开发中会经常用到排序操作&#xff0c;这里提供两种方式供大家参考&#xff0c;对象的sort()方法和…...

力扣(LeetCode)240. 搜索二维矩阵 II(C++)

题目描述 枚举 枚举整个矩阵&#xff0c;找到等于 target 的元素&#xff0c;则 return true &#xff0c;否则 return false。 class Solution { public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int n matrix.size(), m matrix[0]…...

golang defer

文章目录延迟函数的参数在defer语句出现时就已经确定下来了延迟函数没有入参时&#xff0c;延迟函数体内的变量会受到影响延迟函数 *可以* 修改主函数的 *具名* 返回值延迟函数 *无法* 修改主函数的 *匿名* 返回值defer会把声明的 延迟函数以及 函数的入参放到栈上&#xff0c;…...

【Java】线程的死锁和释放锁

线程死锁是线程同步的时候可能出现的一种问题 文章目录1. 线程的死锁1.1 基本介绍1.2 应用案例2. 释放锁2.1 下面的操作会释放锁2.2 下面的操作不会释放锁1. 线程的死锁 1.1 基本介绍 多个线程都占用了对方的锁资源&#xff0c;但不肯相让&#xff0c;导致了死锁&#xff0c;…...

如何使用断点续传上传大文件

概念 大文件上传的需求介绍 不管怎样简单的需求&#xff0c;在量级达到一定层次时&#xff0c;都会变得异常复杂。 文件上传简单&#xff0c;文件变大就复杂 上传大文件时&#xff0c;以下几个变量会影响我们的用户体验 服务器处理数据的能力请求超时网络波动 上传时间会变长…...

【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波

【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波 文章目录【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波1. 前言2. 符号说明3. 三种滤波3.1 全通滤波3.2 低通滤波3.2.1 平滑信号分析3.2.2 广义拉普拉斯平滑滤波器3.3 高通滤波4. 总结1. 前言 GCN&…...

python操作mysql数据库详解

使用Python操作MySQL数据库 MySQL是一种关系型数据库管理系统&#xff0c;它可以用来存储和管理大量的数据。之前介绍了大部分主流数据库&#xff0c;今天将介绍如何使用Python来操作MySQL数据库。 安装MySQL 首先&#xff0c;我们需要安装MySQL服务器&#xff0c;可以从MyS…...

netty群聊系统

1设计思路&#xff1a;启动一个服务端&#xff0c;多个客户端第一个客户端启动时&#xff0c;会告诉服务器上线了第二个客户端启动时&#xff0c;告诉服务器上线&#xff0c;并且通知第一个启动的客户端第三个客户端启动时&#xff0c;告诉服务器上线&#xff0c;并且通知第一个…...

Android 初代 K-V 存储框架 SharedPreferences,旧时代的余晖?

本文已收录到 AndroidFamily&#xff0c;技术和职场问题&#xff0c;请关注公众号 [彭旭锐] 提问。 前言 大家好&#xff0c;我是小彭。 SharedPreferences 是 Android 平台上轻量级的 K-V 存储框架&#xff0c;亦是初代 K-V 存储框架&#xff0c;至今被很多应用沿用。 有的…...

Kali Linux安装失败?5个常见报错解决方案(虚拟机专用版)

Kali Linux虚拟机安装报错实战指南&#xff1a;5个高频问题深度解析 当你兴致勃勃地在VMware里安装Kali Linux准备大展身手时&#xff0c;突然弹出的报错信息就像一盆冷水浇下来。别急着重装——90%的安装问题都有现成解决方案。本文将聚焦虚拟机环境下最棘手的5类安装报错&…...

保姆级教程:在Windows 11上为PyTorch配置CUDA 12.x和cuDNN(含环境变量疑难杂症排查)

Windows 11深度学习环境配置全攻略&#xff1a;从CUDA安装到PyTorch GPU加速实战 每次打开PyCharm准备大展身手时&#xff0c;看到那个令人心碎的False——torch.cuda.is_available()的输出结果&#xff0c;是不是感觉整个深度学习梦想都被泼了冷水&#xff1f;别担心&#xf…...

vLLM-v0.17.1实操手册:Prometheus监控指标接入与告警配置

vLLM-v0.17.1实操手册&#xff1a;Prometheus监控指标接入与告警配置 1. vLLM框架简介 vLLM是一个专为大型语言模型(LLM)设计的高性能推理和服务库&#xff0c;由加州大学伯克利分校的天空计算实验室(Sky Computing Lab)开发&#xff0c;现已发展为社区驱动的开源项目。这个框…...

RWKV7-1.5B-g1a参数详解教程:max_new_tokens/temperature/top_p调优实操手册

RWKV7-1.5B-g1a参数详解教程&#xff1a;max_new_tokens/temperature/top_p调优实操手册 1. 模型简介 rwkv7-1.5B-g1a 是基于新一代 RWKV-7 架构的多语言文本生成模型&#xff0c;特别适合中文场景下的基础问答、文案创作和简短总结任务。作为轻量级模型&#xff0c;它在保持良…...

HP-Socket开发者技能认证考试大纲更新全指南:周期解析与参与攻略

HP-Socket开发者技能认证考试大纲更新全指南&#xff1a;周期解析与参与攻略 【免费下载链接】HP-Socket High Performance TCP/UDP/HTTP Communication Component 项目地址: https://gitcode.com/gh_mirrors/hp/HP-Socket HP-Socket作为高性能TCP/UDP/HTTP通信组件&…...

工厂里EtherCAT从站模块坏了别慌!手把手教你用Startup list和CoE-online快速换新(附配置顺序避坑指南)

工厂EtherCAT从站模块更换实战指南&#xff1a;Startup list与CoE-online的高效应用 当生产线上的EtherCAT从站模块突然罢工&#xff0c;设备维护工程师往往面临两难选择&#xff1a;是临时在线修改参数快速恢复生产&#xff0c;还是彻底解决"即插即用"的配置难题&am…...

UModel:虚幻引擎资源解析工具零基础入门到高级应用指南

UModel&#xff1a;虚幻引擎资源解析工具零基础入门到高级应用指南 【免费下载链接】UEViewer Viewer and exporter for Unreal Engine 1-4 assets (UE Viewer). 项目地址: https://gitcode.com/gh_mirrors/ue/UEViewer 虚幻引擎资源解析是游戏开发与逆向工程领域的关键…...

图表数据提取的智能转换革命:从像素到数据点的精准跨越

图表数据提取的智能转换革命&#xff1a;从像素到数据点的精准跨越 【免费下载链接】WebPlotDigitizer WebPlotDigitizer: 一个基于 Web 的工具&#xff0c;用于从图形图像中提取数值数据&#xff0c;支持 XY、极地、三角图和地图。 项目地址: https://gitcode.com/gh_mirror…...

小白友好!FunASR语音识别镜像部署教程,开箱即用

小白友好&#xff01;FunASR语音识别镜像部署教程&#xff0c;开箱即用 1. 快速了解FunASR语音识别 FunASR是由阿里云推出的开源语音识别工具包&#xff0c;它就像是一个能听懂人说话的智能助手。想象一下&#xff0c;你对着手机说话&#xff0c;它能立刻把你说的话变成文字—…...

Python AI 用例工具部署踩坑实录:Docker镜像体积暴增300%、GPU显存泄漏、模型热加载失败的5个根因与秒级修复方案

第一章&#xff1a;Python AI 用例工具部署的典型失败图谱在真实生产环境中&#xff0c;Python AI 工具链&#xff08;如 LangChain、LlamaIndex、FastAPI 封装的推理服务&#xff09;的部署失败往往并非源于模型能力缺陷&#xff0c;而是由基础设施、依赖冲突与配置漂移引发的…...