首页 / 算法 / 复杂链表的复制(一道算法题)
复杂链表的复制(一道算法题)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了复杂链表的复制(一道算法题),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2295字,纯文字阅读大概需要4分钟。
内容图文
![复杂链表的复制(一道算法题)](/upload/InfoBanner/zyjiaocheng/1208/fd5160562c0f41e3927f15ce16c4f0fb.jpg)
题目是这样的:
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
这道题什么意思呢?它的意思就是说,我有一个节点类型,这个节点类型有三个成员,其中一个成员存放值,另外另个成员分别是两个指针,一个是next指针,指向下一个节点;还有一个是random指针,指向链表中的任意一个节点。这个节点类型跟我们之前见到的节点类型有点不太一样,不一样之处就是多了一个指向任意节点的random指针。别的就没什么不同了。如下图所示:
![技术分享图片](/upload/getfiles/default/2022/11/1/20221101011313881.jpg)
(这图完全是自己用微软自带的画图工具画的,不太好看,但是不影响理解,哈哈~)
理解了题意,现在来写解法。
这道题有两种解法,第一种是使用额外空间的解法,比较简单;另一种是不使用额外空间的解法,写法比较奇妙,但是比较难写;
现在先讲第一种使用额外空间的写法。用额外空间呢,就是使用一个Map。
首先遍历一遍链表,将链表中所有节点都在Map中存储下来。哦,对了,map就是<key,value>类型的一种结构,如果不了解的同学,请自行百度,网上很多关于map的介绍。
代码如下:
cur = pHead;
while(cur != NULL){
map.insert(pair<RanomListNode*, RandomListNode*>(cur, new RandomListNode(cur->value));
cur = cur->next;
}
这只是一个代码片段,里面出现的东西,下面会有完整介绍。
此时,我在map中已经存有和现有链表一样多的节点了,并且节点值也是一样的。只是,我们还没有设置map中节点的next指针和random指针,换言之,这时map中的所有节点是断开的。
如下图:
很明显,我们知道接下来要做什么。就是将这些节点按照题目给出的链表模样串起来。
其次,将拷贝节点按照原链表连接好它们的next指针和random指针。
那么怎么串呢?我们看一下上面两张图,1的next指针连的是2,因此我们的拷贝节点1‘就得连2‘。也就是说,我们需要通过map去找到节点1的拷贝节点1‘,然后通过map去找到1的下一个节点的拷贝节点2‘。这不是很好理解,通过代码展示什么意思:
myMap[cur]->next = myMap[cur->next];
根据代码来看,我们通过myMap[cur]找到cur的拷贝节点,这个拷贝节点的next指针指向了cur节点下一个节点的拷贝节点。这样,就把两个拷贝节点连接起来了。
random指针同理设置。
代码如下:
myMap[cur]->random = myMap[cur->random];
最后一步,返回拷贝链表的头节点。因为,此时拷贝节点都串起来了,形成了完整的链表,只要返回链表头部,就能得到整个拷贝链表了。到此,所有步骤就已经结束了。
下面是完整代码:
#include <iostream>
#include <map>
using namespace std;
struct RandomListNode{
int value;
Node* next;
Node* random;
Node(int value) : value(value), next(NULL), random(NULL){
}
};
class CopyListWithRandom {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
if(pHead == NULL)
return NULL;
map<RandomListNode*, RandomListNode*> myMap;
RandomListNode* cur = pHead;
while(cur != NULL){
myMap.insert(pair<RandomListNode*, RandomListNode*>(cur, new RandomListNode(cur->value)));
cur = cur->next;
}
cur = pHead;
while(cur != NULL){
myMap[cur]->next = myMap[cur->next];
myMap[cur]->random = myMap[cur->random];
cur = cur->next;
}
return myMap[pHead];
}
};
运行结果:
测试代码就自己写一下吧,比较简单。这种写法的关键是要掌握map的使用,别的也没有什么了。
至于不用额外空间的写法,那就更逆天了,下次再写吧,哈哈~
感谢各位大佬的阅读。欢迎评论,欢迎点赞~
================================================================================================================
如果可以的话,打个赏也行啊,哈哈~
一毛两毛也表示万分感谢,哈哈~
下面是我的支付宝及微信二维码
原文:http://blog.51cto.com/chen0547/2288050
内容总结
以上是互联网集市为您收集整理的复杂链表的复制(一道算法题)全部内容,希望文章能够帮你解决复杂链表的复制(一道算法题)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。