leetcode:138. 随机链表的复制

一、题目:

138. 随机链表的复制 - 力扣(LeetCode)

 

函数原型:

struct Node* copyRandomList(struct Node* head)

二、思路

本题是给出一个单链表,单链表的每个结点还额外有一个随机指针,随机指向其他结点,要求复制该链表。

常规情况下复制链表,只需要遍历原链表,新建和原链表相同的结点尾插到新链表即可。

但是该链表有一个随机指针,还需要找到原链表中各个结点随机指针的指向,让新链表中结点的随机指针也指向新链表中的与原链表中相同位置的结点。因此还要在新链表中找到原链表中各个结点随机指针指向的结点,算法为O(N^2),且判断是否为随机指针指向的结点只能通过结点值判断,如果链表中有多个值相同的结点,九不便于判断是否为随机指针指向的结点。

 

上述方法不易实现,此处提供一个全新的思路:

由于新建一个链表每个结点的随机指针不好复制,那么就在原链表上复制每个结点,然后再复制每个结点的随机指针。

先在原链表每个结点后复制一个相同的结点,复制完成后,再次遍历链表,就可以通过当前结点随机指针指向结点的下一个结点找到复制结点随机指针需要指向的结点。最后将每个复制的结点从原链表中拆下来,重新链接组成新的链表即可完成链表的复制。

三、代码

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

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=cur->next->next;
	}

	cur=head;
	while(cur)
	{
		//复制结点的随机指针指向的结点就是当前结点随机指针指向结点的下一结点
		if(cur->random)
			cur->next->random=cur->random->next;
		else
			cur->next->random=NULL;

		cur=cur->next->next;
	}

	cur=head;
	struct Node* newhead=NULL;
	struct Node *tail=NULL;
	while(cur)//拆下复制的结点并恢复原链表,重新链接这些结点
	{
		struct Node* next=cur->next;
		cur->next=next->next;
		if(tail==NULL)
		{
			newhead=tail=next;
		}
		else
		{
			tail->next=next;
			tail=next;
		}
		cur=cur->next;
	}

	return newhead;

}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用VSCode进行Python模块调试

使用VSCode进行Python模块调试 创建测试文件 创建文件test/a/b.py,且当前工作路径为test/ b.py文件内容: def cal(numa, numb):print(int(numa) int(numb))if __name__ "__main__":import sys# 判断系统参数长度是否为4且判断第2个参数是…

【机器学习基础】机器学习的模型评估(评估方法及性能度量原理及主要公式)

🚀个人主页:为梦而生~ 关注我一起学习吧! 💡专栏:机器学习 欢迎订阅!后面的内容会越来越有意思~ 💡往期推荐: 【机器学习基础】机器学习入门(1) 【机器学习基…

【广州华锐互动】VR居家防火逃生模拟演练增强训练的真实性

VR软件开发公司广州华锐互动在消防培训领域已开发了多款VR产品,今天为大家介绍VR居家防火逃生模拟演练系统,这是一种基于虚拟现实技术的消防教育训练设备,通过模拟真实的火灾场景,让使用者身临其境地体验火灾逃生过程,…

Telnet 测试 UDP 端口?

Telnet 并不支持 UDP 端口的测试,可以使用 nc 命令来进行测试。nc 命令两种都支持: TCP # nc -z -v -u [hostname/IP address] [port number] # nc -z -v 192.168.10.12 22 Connection to 192.118.20.95 22 port [tcp/ssh] succeeded! UDP # nc -z -v…

假如我是Langchain专家,你会问什么来测试我的水平

推荐Langchain YouTube 视频排行榜 1. 假如我是Langchain专家,你会问什么来测试我的水平; 作为Langchain专家,您可能需要回答一系列深入和具体的问题,这些问题旨在测试您对Langchain的理解和实际应用能力。以下是一些可能的问题…

浅谈:Flutter现状、与为什么选择Flutter——其实大家都在用只是你不知道罢了

浅谈:谁将会动那些抵制学习还装懂的人的蛋糕 开发环境现状与为什么选择Flutter 我本从不屑于写这种技术外的技术文章,但是今天刷某应用优点上头,想发唯一一篇。这篇文章可能会得罪一些就喜欢地址学新架构的,以及还不了解就开始起哄…

【go】报错整理与解决

文章目录 依赖下载失败checksum mismatch启动报错missing go.sum 依赖下载失败checksum mismatch > go get github.com/hibiken/asynqmon go: downloading github.com/hibiken/asynqmon v0.7.2 go: github.com/hibiken/asynqmonv0.7.2: verifying module: checksum mismatc…

Q learning算法

Q learning算法 代码仓库:https://github.com/daiyizheng/DL/tree/master/09-rl Q Learning是强化学习算法中的一个经典算法。在一个决策过程中,我们不知道完整的计算模型,所以需要我们去不停的尝试。 算法流程 整体流程如下: Q-table 初…

XUbuntu22.04之安装pkg-config(一百九十二)

简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生…

自定义GPT已经出现,并将影响人工智能的一切,做好被挑战的准备了吗?

原创 | 文 BFT机器人 OpenAI凭借最新突破:定制GPT站在创新的最前沿。预示着个性化数字协助的新时代到来,ChatGPT以前所未有的精度来满足个人需求和专业需求。 从本质上讲,自定义GPT是之前的ChatGPT的高度专业化版本或代理,但自定…

kafka单节点创建 topic 超时

1.根据之前的知道,安装kafka的时候改了config的server.properies文件中的listeners配置 之前这一行是没有注释掉的,结果创建topic的时候时钟报错连接超时 结果资料,发现就是因为listeners的问题 https://blog.csdn.net/weixin_42133361/art…

【2013年数据结构真题】

highlight: a11y-dark 41题 王道解析: 算法的策略是从前向后扫描数组元素,标记出一个可能成为主元素的元素Num 。然后重新计数,确认Num是否是主元素。算法可分为以下两步: 选取候选的主元素:依次扫描所给数组中的每个…

CCNA课程实验-14-Final_Lab

目录 实验条件网络拓朴需求 配置实现1. 配置PC1~3, DHCP_Server的vlan2. VLAN10、20的网关为MSW1对应的SVI,VLAN30、40的网关为MSW2对应的SVI;3. 配置5台交换机之间线路均为Trunk4. 配置5台交换机均启用Rapid-PVST(RSTP)5. 配置DHCP Server,创…

CCF ChinaSoft 2023 论坛巡礼|自动驾驶仿真测试论坛

2023年CCF中国软件大会(CCF ChinaSoft 2023)由CCF主办,CCF系统软件专委会、形式化方法专委会、软件工程专委会以及复旦大学联合承办,将于2023年12月1-3日在上海国际会议中心举行。 本次大会主题是“智能化软件创新推动数字经济与社…

Outlook如何精准搜索邮件

说明: 使用Outlook默认的搜索时,会出来很多无关的信息,对搜索邮件带来很大的不便,下面介绍一个使用精准搜索的方法。 操作指引: 1、在outlook左上角,进行如下操作,打开“其他命令” 2、打开快…

基于RFbeam的V-LD1-60GHz毫米波雷达传感器数据获取(通过UART串口来控制模块)

基于RFbeam的V-LD1-60GHz毫米波雷达传感器数据获取(通过UART串口来控制模块) 文章目录 V-LD1命令发送消息回复通信示例雷达数据获取宏定义通信代码运行效果附录:压缩字符串、大小端格式转换压缩字符串浮点数压缩Packed-ASCII字符串 大小端转…

大数据知识图谱项目——基于知识图谱的电影问答系统(超详细讲解及源码)

大数据知识图谱项目——基于知识图谱的电影问答系统(超详细讲解及源码) 一、项目概述 知识图谱是将知识连接起来形成的一个网络。由节点和边组成,节点是实体,边是两个实体的关系,节点和边都可以有属性。知识图谱除了…

【物联网】BDS/GNSS 全星座定位导航模块——ATGM332D-5N

随着科技的不断进步,导航系统已经成为我们日常生活中不可或缺的一部分。传统的导航系统往往只提供基本的地图和路线规划,对于一些特殊需求或个性化定位并不够满足。全星座定位导航模块的出现,为我们带来了全新的导航体验。通过结合星座学说和…

【Liunx】部署WEB服务:Apache

【Liunx】部署WEB服务:Apache 概述Apache1.介绍2.Apache文件路径3.Apache详解(1)安装Apache(2)启动Apache(3)配置文件a.Apache主配置文件:vim /etc/httpd/conf/httpd.conf信息:b.基于主机头的虚拟主机 (4)开始演示:a.新建两个网站根目录b.分别…

JavaScript从入门到精通系列第三十七篇:详解JavaScript中文档的加载顺序

文章目录 一:文档加载说明 1:回顾一个代码 2:问题分析和说明 二:如何给JS换个位置? 1:过程分析 2:代码编写 3:运行结果 4:解释说明 大神链接:作者有幸…