[C/C++]数据结构 链表OJ题:随机链表的复制

题目描述:

        给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。

        构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。返回复制链表的头节点。

        例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有 x.random --> y 。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val,random_index] 表示:

  • val:一个表示 Node.val 的整数。
  • random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为  null 。

你的代码只接受原链表的头节点 head 作为传入参数

示例1:

输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2:

输入:head = [[1,1],[2,1]]
输出:[[1,1],[2,1]]

示例3:

输入:head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

解题思路:

        这个题目描述这么长,其实就是说让我们完全复制一个和原链表相同的链表.这个题麻烦的地方是每个结点都有一个随机指针指向链表的随机一个位置.

思路一: (不推荐麻烦)

        遍历一遍原链表,先不管结点中random的指向问题,把所有malloc的结点的random指向NULL,复制出一条新链表,再解决random指向的问题.

        对于random的指向问题,我们可以遍历原链表,找每个结点的random指向的是链表中的第几个结点

例如:

        原链表第一个结点的random指向了原链表中的第五个结点,那我们就让我们创建的新链表中的第一个结点的random指向先链表中的第五个结点,以此类推,这样就可以解决新链表的random指向问题,但是这样处理每个结点的random都需要遍历一次原链表和新链表,时间复杂度达到了O(n^2),

下面这个思路可以把时间复杂度优化到O(n);

思路二:  (最优解)

        思路1是直接复制了一个新链表,而处理新链表的random并不能让其指向原链表的结点.只能指向自己创建的结点,这样就只能靠random指向的结点在原链表中的位置处理新结点的random指向.

所以我们可以在原链表每个结点后面插入一个相同的结点,这样处理结点的random问题就会简单很多.

如图所示:

        拷贝的结点都在原结点之后,这样原结点random所指结点的下一个结点便是拷贝结点的random应指向的结点

        处理好random问题后,只需要恢复原链表和分离拷贝链表就好了

   1 . 拷贝结点到原结点后面

    struct Node* cur=head;while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;copy->next=cur->next;cur->next=copy;cur=copy->next;}

   2. 处理random指针

    cur=head;while(cur){struct Node* copy=cur->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=copy->next;}

  3. 分离拷贝链表和复原原链表

 struct Node* newhead=NULL,*tail=NULL;cur=head;while(cur){struct Node* copy=cur->next;struct Node* next=copy->next;if(tail==NULL){tail=newhead=copy;}else{tail->next=copy;tail=tail->next;}cur->next=next;cur=next;}

  题目参考代码:


struct Node* copyRandomList(struct Node* head) {//拷贝结点到原结点后面struct Node* cur=head;while(cur){struct Node* copy=(struct Node*)malloc(sizeof(struct Node));copy->val=cur->val;copy->next=cur->next;cur->next=copy;cur=copy->next;}//处理random指针cur=head;while(cur){struct Node* copy=cur->next;if(cur->random==NULL){copy->random=NULL;}else{copy->random=cur->random->next;}cur=copy->next;}//分离拷贝链表和复原原链表struct Node* newhead=NULL,*tail=NULL;cur=head;while(cur){struct Node* copy=cur->next;struct Node* next=copy->next;if(tail==NULL){tail=newhead=copy;}else{tail->next=copy;tail=tail->next;}cur->next=next;cur=next;}return newhead;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/197654.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从零开始 通义千问大模型本地化到阿里云通义千问API调用

从零开始 通义千问大模型本地化到阿里云通义千问API调用 一、通义千问大模型介绍 何为“通义千问”? “通义千问大模型”是阿里云推出的一个超大规模的语言模型,具有强大的归纳和理解能力,可以处理各种自然语言处理任务,包括但…

Oracle主备切换,ogg恢复方法(集成模式)

前言: 文章主要介绍Oracle数据库物理ADG主备在发生切换时(switchover,failover),在主库运行的ogg进程(集成模式)如何进行恢复。 测试恢复场景,因为集成模式不能在备库配置,所以场景都是基于主库端: 1 主备发生switchover切换,主库…

VUE(一)

1.vue简介 英文官网: Vue.js - The Progressive JavaScript Framework | Vue.js 中文官网: Vue.js - 渐进式 JavaScript 框架 | Vue.js 2.Vue的特点 3.初识VUE 在官网下载VUE.js,有两个版本&#xff0c;一个开发一个生产 <!DOCTYPE html> <html lang"en"…

贝锐蒲公英云AP,企业WiFi功能如何使用?

1. 功能介绍 基于WPA2-EAP安全认证技术&#xff0c;为企业提供了一套易用安全的企业无线网络,实现企业员工通过蒲公英客户端一键连接企业无线WiFi。自动分配一人一帐一密&#xff0c;无需配置证书或手动输入密码&#xff0c;减少沟通成本&#xff0c;方便快捷&#xff0c;提高…

前置语音群呼与语音机器人群呼哪个更好

最近通过观察自己接到的营销电话&#xff0c;通过语音机器人外呼的量应该有所下降。同时和客户交流获取到的信息&#xff0c;也是和这个情况类似&#xff0c;很多AI机器人群呼的量转向了OKCC前置语音群呼。询问原因&#xff0c;说是前置语音群呼转化更快&#xff0c;AI机器人群…

Android修行手册-POI操作中文API文档

Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列Scratch编程案例软考全系列Unity3D学习专栏蓝桥系列ChatGPT和AIGC &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分…

pm2在Windows环境中的使用

pm2 进程管理工具可以Windows操作系统上运行&#xff0c;当一台Windows电脑上需要运行多个进程时&#xff0c;或者运维时需要运行多个进程以提供服务时。可以使用pm2&#xff0c;而不再是使用脚本。 1. 使用PM2管理进程 1.1. 启动PM2项目 1.1.1. 直接启动项目 参数说明&…

PostgreSQL 数据定义语言 DDL

文章目录 表创建主键约束非空唯一约束检查约束外键约束默认值约束 触发器表空间构建表空间 视图索引索引的基本概念索引的分类创建索引 物化视图 表创建 PostgreSQL表的构建语句与所有数据库都一样&#xff0c;结构如下&#xff0c;其核心在于构建表时&#xff0c;要指定上一些…

ACWSpring1.3

首先,前端写ajax写上我们的访问路径(就在我们前端的源代码里面),我们建了两个包pkController用于前端页面url映射过来一层一层找到我们的RestController返回bot1里面有键值,返回的这就是一个session对象bot1这个map.前端拿到我们bot1里的两个值给到我们前端显示出来 1准备页面:…

Linux:补充一些常用命令

Linux&#xff1a;补充一些常用命令 1. free -h2. df -lh3. du -sh *4. uname -a5. which6. mvn install 编译打包7. find -name *.jar8. cd -9. nohup java -jar *.jar &10. ps -ef|grep java11. netstat -ntlp 1. free -h free 命令显示系统使用和空闲的内存情况&#x…

Flutter笔记:缩放手势

Flutter笔记 缩放手势 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/134485138 目 录 1. 概述2. 缩放手…

Java多线程核心技术第一阶段-Java多线程基础 02

接上篇&#xff1a;Java多线程核心技术第一阶段-Java多线程基础 01 3.3 清除中断状态的使用场景 this.interrupted()方法具有清除状态标志值的功能&#xff0c;借用此特性可以实现一些效果。 【示例3.3.1】在MyThread4线程中向list1和list2存放数据&#xff0c;基于单一职责原…

docker-compose 部署 MySQL 8

目录 前言MySQL 配置文件(my.cnf)docker-compose.yml安装卸载 前言 Windows/Linux 系统通过 docker-compose 部署 MySQL8.0。 MySQL 配置文件(my.cnf) # 服务端参数配置 [mysqld] usermysql # MySQL启动用户 default-storage-engineINNODB # 创建新表时…

【脑与认知科学】【n-back游戏】

请参考课堂内容&#xff0c;设计一种测试工作记忆的实验方法&#xff0c;并选择三位同学作为被试测试工作记忆。请画出实验流程图&#xff0c;叙述实验测试目标&#xff0c;并分析实验结果。 举例&#xff1a;一般我们选择n_back来测试对数字或字母的记忆&#xff0c;选择色块实…

springboot实现在线人数统计

在线人数统计 笔者做了一个网站&#xff0c;需要统计在线人数。 在线有两种&#xff1a; 一、如果是后台系统如果登录算在线&#xff0c;退出的时候或者cookie、token失效的时候就算下线 二、如果是网站前台&#xff0c;访问的时候就算在线 今天我们来讲一下第2种情况&…

SQL零基础入门教程,贼拉详细!贼拉简单! 速通数据库期末考!(九)

UNION ALL UNION ALL 用于合并两个或多个 SELECT 语句的结果。 请注意&#xff0c;UNION ALL 合并的每个 SELECT 语句必须是查询相同数量&#xff0c;相同数据类型的字段&#xff0c;且顺序也必须一致。另外结果集中的列名总是等于 UNION ALL 中第一个 SELECT 语句中的列名。 …

数据结构与算法-图

图 &#x1f388;2.图的存储结构&#x1f4d6;2.4.2邻接表的存储✅2.4.2.1逆邻接表✅2.4.2.2邻接表存储结构的定义✅2.4.2.3邻接表存储结构的类定义✅2.4.2.4创建n个顶点m条边的无向网✅2.4.2.5创建n个顶点m条边的有向网✅2.4.2.6定位操作-查找定点信息在顶点数组中的下标✅2.4…

3GPP协议解读(一)_23.501_23.502_PDU Session_SMF与UDP的交互

UE发起计算服务申请后&#xff0c;网络侧处理的流程 UE发起服务的流程&#xff1a;service request网络侧处理服务涉及的通信数据通过PDU Session进行传输&#xff0c;涉及到SMF与UPF的交互。PDU Session的建立、管理全部由SMF&#xff08;Session Management Function&#x…

【uniapp】 video视频层级、遮挡其他弹窗或顶部导航 使用nvue覆盖

uniapp 顶部导航和弹窗被video遮挡解决办法 第一步&#xff1a;配置 subNVues {"path": "pages/index/index","style": {"navigationBarTitleText": "uni-app","navigationStyle": "custom","app-…

SQL零基础入门教程,贼拉详细!贼拉简单! 速通数据库期末考!(八)

FULL OUTER JOIN 除了前面讲到的 INNER JOIN&#xff08;内连接&#xff09;、LEFT JOIN&#xff08;左连接&#xff09;、RIGHT JOIN&#xff08;右连接&#xff09;&#xff0c;还有另外一种关联方式&#xff0c;即 FULL OUTER JOIN&#xff08;全外连接&#xff09; FULL O…