力扣LeetCode138. 复制带随机指针的链表 两种解法（C语言实现）

目录

题目链接

题目分析

 题目定位：

解题思路

解题思路1（粗暴但是复杂度高）

 解题思路2（巧妙并且复杂度低）

题目链接

138. 复制带随机指针的链表icon-default.png?t=N7T8https://leetcode-cn.com/problems/copy-list-with-random-pointer/

题目分析

 题目定位：

本题属于链表中较为综合的题目，考验做题者的思想以及用代码实现的能力，能够真正理解并做出此题需要对链表有相对熟练的掌握度。

话不多说，先来分析题目：

题目是想让我们构造一个链表的拷贝，也就是开辟一块一模一样的链表，但是本题中的链表，又和普通的单链表不一样，如图：

我们发现，链表中每一个节点中的结构体成员除了val和next之外，还有一个random，而random是指向链表中的任意一个节点，甚至可以是NULL。

因此要拷贝这个链表的难度就在于，如何使拷贝的链表中每一个节点的random指向其对应的节点呢？

解题思路

解题思路1（粗暴但是复杂度高）

第1步.先忽略原链表的random指针，对其进行复制，如图：

(1)定义两个struct Node*类型的指针copyhead和copytail来储存复制链表的头和尾，并初始化为NULL；并且定义一个struct Node*类型的指针cur指向head

(2)若原链表不为空，则此时cur指向第一个节点。用malloc开辟一块空间作为复制的第一个节点，并定义一个copy指针来保存，并将copy->val改为cur->val，并让copyhead和copytail指向copy节点

(3)让cur移向下一个节点。用malloc开辟一块空间作为复制的第二个节点，并让copy指向它，并将copy->val改为cur->val，先让copytail->next指向copy来连接两个节点，再让copytail指向copy节点(更新尾节点)。

像这样一直循环下去直到cur指向NULL，循环结束，最后再让copytail->next = NULL，此时便完成了第一步的复制操作

此时我们便可以根据图解来写代码

struct Node* copyRandomList(struct Node* head) {//1.忽略random复制链表struct Node* cur = head;struct Node* copyhead = NULL;struct Node* copytail = NULL;while(cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node))；copy->val = cur->val;if(copyhead == NULL){copyhead = copy;copytail = copy;}else{//先连接copytail->next = copy;//再指向copycopytail = copy;}cur = cur->next;}copytail->next = NULL;
}

第2步.处理拷贝链表的random指针

(1)查找原链表中的random指向的节点到底是第几个节点，并定义一个变量pos来记录下来

①如果原链表random指向NULL，则不需要找pos

②如果原链表的random指向链表中的节点，每次循环开始可以初始化一个新的指针newcur=head，再对newcur进行迭代，每当newcur向后走一次，pos加一，直到newcur == cur->random的时候，循环结束，举一个例子：

 (2)用一个循环来使拷贝链表中random指向其对应的节点

①如果原链表的random指向NULL，那么便很简单：拷贝的random直接置为NULL；

②如果原链表的random指向链表中的节点，每次循环开始可以初始化一个新的指针newcopy=copyhead,那么拷贝的random则可以通过一个循环来找到pos所对应的第几个节点，接着上面的例子：

根据图解我们可以写出代码：

struct Node* copyRandomList(struct Node* head) {//1.忽略random复制链表struct Node* cur = head;struct Node* copyhead = NULL;struct Node* copytail = NULL;while (cur){struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;if (copyhead == NULL){copyhead = copy;copytail = copy;}else{//先连接copytail->next = copy;//再指向copycopytail = copy;}cur = cur->next;copytail->next = NULL;}//2.处理拷贝链表的random指针cur = head;struct Node* copy = copyhead;while (cur){int pos = 0;if (cur->random == NULL){copy->random = NULL;}//找到cur的random指向对应的第几个节点else{//让newcur和newcopy重新指向第一个节点struct Node* newcur = head;struct Node* newcopy = copyhead;while (newcur != cur->random){newcur = newcur->next;pos++;}//使copy的random指向对应的第pos个节点while (pos--){newcopy = newcopy->next;}copy->random = newcopy;}//cur和copy向后走cur = cur->next;copy = copy->next;}return copyhead;
}

 题解一总结：优点是这种思路比较容易想到并且理解；缺点是由于找到原链表找到random指向的节点的pos的过程，每个节点的复杂度为O(n)，又有n个节点，因此这种解法的时间复杂度为O(n²)，并不是一个优秀的解法，接下来将为大家讲另一种优秀的解法。

 解题思路2（巧妙并且复杂度低）

第1步 把拷贝节点连接再原节点的后面

用这种方式处理是为了方便找到拷贝链表的random应该指向第几个节点，random指向的这个节点的下一个节点就是拷贝链表要找的random节点

根据图解我们可以写出代码：

//1.链接链表struct Node* cur = head;while(cur){//提前储存原链表下一个节点的地址struct Node* next = cur->next;//为原链表的拷贝开辟空间struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;//链接原链表和拷贝节点cur->next = copy;copy->next = next;//迭代往下走cur = next;}

 第2步 拷贝原链表的random节点

 (1)若原链表的节点的random指向NULL，拷贝节点的random也指向NULL

(2)若原链表的节点random指向原链表的其中一个节点，那么random指向的这个节点的下一个节点就是拷贝链表要找的random，以原链表二个节点为例：

(3)实现后题解如下

根据图解我们可以写出代码：

//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步 将拷贝节点与原链表分开

(1)用cur和copy指针来分别使原链表和拷贝链表的节点向后迭代，由于copy随着cur向后迭代，一直跟在cur的后面

因此循环外初始化cur = head，循环内初始化copy = cur->next;

 (2)为原链表定义一个next来连接链表；为拷贝链表定义一个copyhead和copytail来返回和连接链表，当原链表第一个节点不为空，才能保证copy的第一个节点不为空，因此copyhead和copytail先置空

循环外初始化copytail = copyhead = NULL，循环内初始化next = copy->next, 

(3)当cur指向第一个节点时，进入循环，此时copyhead和copytail为空，使其指向拷贝链表的第一个节点，再使cur->next = next，将cur和next连接起来，并使cur=next往后走，

 若cur不为空，再之后就是让copy=cur->next，next = copy->next

  捋清楚结构就可以写出循环体框架：

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

(4)当cur指向第二个节点时，copyhead和copytail此时不为空，copy也指向拷贝的第二个节点，因此用copytail->next = copy连接两节点，再使copytail = copy使其向后迭代

捋清关系我们便可以补全循环体

//3.将拷贝节点与原链表分开cur = head;struct Node* copyhead = NULL;struct Node* copytail = NULL;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;if(copyhead == NULL){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copy;}cur->next = next;cur = next;}

完整代码： 

struct Node* copyRandomList(struct Node* head) {//1.链接链表struct Node* cur = head;while(cur){//提前储存原链表下一个节点的地址struct Node* next = cur->next;//为原链表的拷贝开辟空间struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;//链接原链表和拷贝节点cur->next = copy;copy->next = next;//迭代往下走cur = 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.将拷贝节点与原链表分开cur = head;struct Node* copyhead = NULL;struct Node* copytail = NULL;while(cur){struct Node* copy = cur->next;struct Node* next = copy->next;if(copyhead == NULL){copyhead = copytail = copy;}else{copytail->next = copy;copytail = copy;}cur->next = next;cur = next;}return copyhead;
}

 题解二总结：由于第二种解题思路用巧妙的连接方式，使拷贝链表的random不需要通过对原链表的每一个节点遍历也能找到，大大降低了时间复杂度，这种解法的时间复杂度为O(n)。

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

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

相关文章

【STL详解 —— list的介绍及使用】

【STL详解 —— list的介绍及使用】

STL详解 —— list的介绍及使用 list的介绍list的介绍使用list的构造list iterator的使用list capacitylist element accesslist modifiers 示例list的迭代器失效 list的介绍 list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭…
阅读更多...
分类预测 | Matlab实现基于迁移学习和GASF-CNN-Mutilhead-Attention格拉姆角场和卷积网络多头注意力机制多特征分类预测/故障识别

分类预测 | Matlab实现基于迁移学习和GASF-CNN-Mutilhead-Attention格拉姆角场和卷积网络多头注意力机制多特征分类预测/故障识别

分类预测 | Matlab实现基于迁移学习和GASF-CNN-Mutilhead-Attention格拉姆角场和卷积网络多头注意力机制多特征分类预测/故障识别 目录 分类预测 | Matlab实现基于迁移学习和GASF-CNN-Mutilhead-Attention格拉姆角场和卷积网络多头注意力机制多特征分类预测/故障识别分类效果基…
阅读更多...
自动化运维工具Ansible

自动化运维工具Ansible

ansible 主要的意义在于可以 提高运维工作效率，降低成本提高准确度 资料 Ansible中文权威指南 离线安装 wget https://github.com/ansible/ansible/archive/refs/tags/v2.16.5.tar.gz tar -zxvf v2.16.5.tar.gz cd ansible-v2.16.5 python setup.py install 主要…
阅读更多...
jmeter使用之生成html测试报告

jmeter使用之生成html测试报告

测试的最终结果是需要给出一份报告，那么在用jmeter测试时怎么生成一份报告呢，以下针对jmeter如何生成html报告进行简单介绍 一、首先把测试脚本写好二、利用命令生成html报告 命令：jmeter -n -t 【Jmx脚本位置】-l 【结果文件result.jtl存放…
阅读更多...
2001-2022年全国各省产业链现代化水平测算(两种方法)-含原始数据、计算结果及do代码

2001-2022年全国各省产业链现代化水平测算(两种方法)-含原始数据、计算结果及do代码

01、数据简介 各省份的产业链现代化水平是一个综合性的评估指标，它涉及到多个因素，包括技术创新、产业升级、生产效率、产业结构优化等方面。这个指标可以用来衡量一个省份在产业链现代化进程中的发展水平和竞争力。该数据揭示了中国省份在推动产业现代…
阅读更多...
【C++题解】 问题：1109 - 加密四位数

【C++题解】 问题：1109 - 加密四位数

问题：1109 - 加密四位数 类型：基础问题、拆位求解 题目描述： 某军事单位用 4 位整数来传递信息，传递之前要求先对这个 4 位数进行加密。加密的方式是每一位都先加上 5 然后对 10 取余数，再将得到的新数颠倒过来。 例…
阅读更多...
迈威通信MaxGate800系列工业边缘计算网关，算力硬核中枢的巅峰之作

迈威通信MaxGate800系列工业边缘计算网关，算力硬核中枢的巅峰之作

随着人们对工业物联网领域的深入了解与实践，越来越多的企业开始寻求将计算业务从云端迁移至网络边缘处理与执行。然而，在实际应用中，开发者面临着诸多挑战。为了解决这些问题，迈威通信MaxGate800系列工业智能网关应运而生。 MaxG…
阅读更多...
2024年MathorCup数学建模C题物流网络分拣中心货量预测及人员排班解题文档与程序

2024年MathorCup数学建模C题物流网络分拣中心货量预测及人员排班解题文档与程序

2024年第十四届MathorCup高校数学建模挑战赛 C题 物流网络分拣中心货量预测及人员排班 原题再现： 电商物流网络在订单履约中由多个环节组成，图1是一个简化的物流网络示意图。其中，分拣中心作为网络的中间环节，需要将包按照不同流…
阅读更多...
分布式技术--------------ELK大规模日志实时收集分析系统

分布式技术--------------ELK大规模日志实时收集分析系统

目录 一、ELK日志分析系统 1.1ELK介绍 1.2ELK各组件介绍 1.2.1ElasticSearch 1.2.2Kiabana 1.2.3Logstash 1.2.4可以添加的其它组件 1.2.4.1Filebeat filebeat 结合logstash 带来好处 1.2.4.2缓存/消息队列（redis、kafka、RabbitMQ等） 1.2.4.…
阅读更多...
ChatGPT深度科研应用、数据分析及机器学习、AI绘图与高效论文撰写

ChatGPT深度科研应用、数据分析及机器学习、AI绘图与高效论文撰写

2022年11月30日，可能将成为一个改变人类历史的日子——美国人工智能开发机构OpenAI推出了聊天机器人ChatGPT3.5，将人工智能的发展推向了一个新的高度。2023年4月，更强版本的ChatGPT4.0上线，文本、语音、图像等多模态交互方式使其在…
阅读更多...
【opencv】示例-neural_network.cpp 使用机器学习模块创建并训练一个简单的多层感知机（神经网络）模型...

【opencv】示例-neural_network.cpp 使用机器学习模块创建并训练一个简单的多层感知机（神经网络）模型...

#include <opencv2/ml/ml.hpp> // 引入OpenCV的机器学习模块using namespace std; // 使用标准命名空间 using namespace cv; // 使用OpenCV命名空间 using namespace cv::ml; // 使用OpenCV机器学习命名空间int main() {//创建随机训练数据Mat_<float> data(100, …
阅读更多...
部署HDFS集群（完全分布式模式、hadoop用户控制集群、hadoop-3.3.4+安装包）

部署HDFS集群（完全分布式模式、hadoop用户控制集群、hadoop-3.3.4+安装包）

目录 前置 一、上传&解压 &#xff08;一 &#xff09;上传 &#xff08;二&#xff09;解压 二、修改配置文件 &#xff08;一&#xff09;配置workers文件 &#xff08;二&#xff09;配置hadoop-env.sh文件 &#xff08;三&#xff09;配置core-site.xml文件 &…
阅读更多...
JS sort方法踩坑

JS sort方法踩坑

JavaScript的sort()方法在默认情况下将数组元素视为字符串进行排序&#xff0c;而不是按照数字的大小。因此&#xff0c;对于包含数字的数组&#xff0c;sort()方法会按照字符串的排序规则进行排序。 例如&#xff0c;对于[2, 11]这个数组&#xff0c;按照字符串的排序规则&…
阅读更多...
从 iPhone 上的短信中恢复已删除的图片的可靠方法

从 iPhone 上的短信中恢复已删除的图片的可靠方法

您可能在浏览消息聊天时不小心删除了一些文本和照片。事实上&#xff0c;如果这些消息对你来说意义重大&#xff0c;那对你来说可能会很麻烦。当发生意外情况时&#xff0c;您可能不想恢复整个聊天&#xff0c;而是恢复其中的附件。 好了&#xff0c;这篇文章主要是讲如何灵活…
阅读更多...
Kubernetes学习笔记12

Kubernetes学习笔记12

k8s核心概念&#xff1a;控制器&#xff1a; 我们删除Pod是可以直接删除的&#xff0c;如果生产环境中的误操作&#xff0c;Pod同样也会被轻易地被删除掉。 所以&#xff0c;在K8s中引入另外一个概念&#xff1a;Controller&#xff08;控制器&#xff09;的概念&#xff0c;…
阅读更多...
AI PC元年，华为的一张航海图、一艘渡轮和一张船票

AI PC元年，华为的一张航海图、一艘渡轮和一张船票

今天&#xff0c;从学术研究者到产业投资者&#xff0c;无不认为大模型掀起了一场人工智能的完美风暴。 所谓“完美风暴”&#xff0c;指的是一项新技术的各个要素&#xff0c;以新的方式互相影响、彼此加强&#xff0c;组合在一起形成了摧枯拉朽般的力量。 而我们每个人&#…
阅读更多...
【C++成长记】C++入门 | 类和对象（上） |面向过程和面向对象初步认识、类的引入、类的定义、类的访问限定符及封装

【C++成长记】C++入门 | 类和对象（上） |面向过程和面向对象初步认识、类的引入、类的定义、类的访问限定符及封装

&#x1f40c;博主主页&#xff1a;&#x1f40c;​倔强的大蜗牛&#x1f40c;​ &#x1f4da;专栏分类&#xff1a;C❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 一、面向过程和面向对象初步认识 C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题的步…
阅读更多...
你的高佣副业不二之选，开始流量卡推广，一文看懂号卡推广

你的高佣副业不二之选，开始流量卡推广，一文看懂号卡推广

在这个信息化的时代&#xff0c;网络已成为人们生活中不可或缺的一部分。然而&#xff0c;在享受着便捷与高效的同时&#xff0c;我们也必须面对一个现实问题&#xff0c;也就是高昂的流量费用。为了解决这一困扰广大用户的痛点&#xff0c;我们今天带来了一个极具吸引力的机会…
阅读更多...
Sonatype Nexus 服务器迁移

Sonatype Nexus 服务器迁移

因为服务器的升级和调整&#xff0c;有时候会对安装 Sonatype Nexus 的服务器进行迁移到新服务器上。 从技术架构上来说&#xff0c;Sonatype Nexus 我们使用的是 AWS 的存储&#xff0c;所以我们并不需要拷贝大量的数据。 文件夹结构 在备份和恢复之前&#xff0c;我们需要…
阅读更多...
11 Php学习：函数

11 Php学习：函数

PHP 内建函数Array 函数 PHP Array 函数是 PHP 核心的组成部分。无需安装即可使用这些函数。 创建 PHP 函数 当您需要在 PHP 中封装一段可重复使用的代码块时&#xff0c;可以使用函数。下面详细解释如何创建 PHP 函数并举例说明。 创建 PHP 函数的语法 PHP 函数的基…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023