复杂链表的复制(一道算法题)

c/c++

浏览数:14

2019-9-11

这是一道算法题。想写篇blog记录一下这道题的解法。
题目是这样的:
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
这道题什么意思呢?它的意思就是说,我有一个节点类型,这个节点类型有三个成员,其中一个成员存放值,另外另个成员分别是两个指针,一个是next指针,指向下一个节点;还有一个是random指针,指向链表中的任意一个节点。这个节点类型跟我们之前见到的节点类型有点不太一样,不一样之处就是多了一个指向任意节点的random指针。别的就没什么不同了。如下图所示:

(这图完全是自己用微软自带的画图工具画的,不太好看,但是不影响理解,哈哈~)
理解了题意,现在来写解法。
这道题有两种解法,第一种是使用额外空间的解法,比较简单;另一种是不使用额外空间的解法,写法比较奇妙,但是比较难写;
现在先讲第一种使用额外空间的写法。用额外空间呢,就是使用一个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的使用,别的也没有什么了。

至于不用额外空间的写法,那就更逆天了,下次再写吧,哈哈~

感谢各位大佬的阅读。欢迎评论,欢迎点赞~

================================================================================================================
如果可以的话,打个赏也行啊,哈哈~
一毛两毛也表示万分感谢,哈哈~

                                                 下面是我的支付宝及微信二维码

作者:BarnabyRoss