这是一道算法题。想写篇博客记录一下这道题的解法。
题目是这样的:
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的头。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
这道题什么意思呢?它的意思就是说,我有一个节点类型,这个节点类型有三个成员,其中一个成员存放值,另外另个成员分别是两个指针,一个是下一指针,指向下一个节点;还有一个是随机指针,指向链表中的任意一个节点。这个节点类型跟我们之前见到的节点类型有点不太一样,不一样之处就是<>强多了一个指向任意节点的随机指针强。别的就没什么不同了。如下图所示:
(这图完全是自己用微软自带的画图工具画的,不太好看,但是不影响理解,哈哈~)
理解了题意,现在来写解法。
这道题有两种解法,第一种是使用额外空间的解法,比较简单,另一种是不使用额外空间的解法,写法比较奇妙,但是比较难写;
现在先讲第一种使用额外空间的写法。用额外空间呢,就是使用一个地图。
<强>首先遍历一遍链表,将链表中所有节点都在地图中存储下来强。哦,对了,地图就是& lt;关键,value>类型的一种结构,如果不了解的同学,请自行百度,网上很多关于地图的介绍。
代码如下:
<代码> cur=pHead;
而(坏蛋!=NULL) {
map.insert (pair
这只是一个代码片段,里面出现的东西,下面会有完整介绍。
此时,我在地图中已经存有和现有链表一样多的节点了,并且节点值也是一样的只。是,我们还没有设置地图中节点的下一指针和随机指针,换言之,这地图中时的所有节点是断开的。
如下图:
很明显,我们知道接下来要做什么。就是将这些节点按照题目给出的链表模样串起来。
<强>其次,将拷贝节点按照原链表连接好它们的下一个指针和随机指针。
那么怎么串呢?我们看一下上面两张图,1的下一指针连的是2,因此我们的拷贝节点1”就得连2》。也就是说,我们需要通过地图去找到节点1的拷贝节点1”,然后通过地图去找到1的下一个节点的拷贝节点2》。这不是很好理解,通过代码展示什么意思:
<代码>关联(坏蛋)→下=关联(cur→下一个);
根据代码来看,<强>我们通过关联(坏蛋)找到坏蛋的拷贝节点,这个拷贝节点的下一指针指向了坏蛋节点下一个节点的拷贝节点。这样,就把两个拷贝节点连接起来了。
随机指针同理设置。
代码如下:
<代码>关联(坏蛋)→随机=关联(cur→随机);
<强>最后一步,返回拷贝链表的头节点强。因为,此时拷贝节点都串起来了,形成了完整的链表,只要返回链表头部,就能得到整个拷贝链表了。到此,所有步骤就已经结束了。
下面是完整代码:
<代码> # include & lt; iostream>
# include & lt; map>
使用名称空间性病;
struct RandomListNode {
int值;
节点*下;
节点*随机;
节点(int值):价值(价值)、下(NULL),随机(NULL) {
}
}；
类CopyListWithRandom {
公众:
RandomListNode *克隆(RandomListNode * pHead)
{
如果(pHead==NULL)
返回NULL;
map
运行结果:
测试代码就自己写一下吧,比较简单。这种写法的关键是要掌握地图的使用,别的也没有什么了。
至于不用额外空间的写法,那就更逆天了,下次再写吧,哈哈~
