復(fù)雜鏈表的復(fù)制（一道算法題）

這是一道算法題。想寫(xiě)篇blog記錄一下這道題的解法。
題目是這樣的：
輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。（注意，輸出結(jié)果中請(qǐng)不要返回參數(shù)中的節(jié)點(diǎn)引用，否則判題程序會(huì)直接返回空）
這道題什么意思呢？它的意思就是說(shuō)，我有一個(gè)節(jié)點(diǎn)類型，這個(gè)節(jié)點(diǎn)類型有三個(gè)成員，其中一個(gè)成員存放值，另外另個(gè)成員分別是兩個(gè)指針，一個(gè)是next指針，指向下一個(gè)節(jié)點(diǎn)；還有一個(gè)是random指針，指向鏈表中的任意一個(gè)節(jié)點(diǎn)。這個(gè)節(jié)點(diǎn)類型跟我們之前見(jiàn)到的節(jié)點(diǎn)類型有點(diǎn)不太一樣，不一樣之處就是多了一個(gè)指向任意節(jié)點(diǎn)的random指針。別的就沒(méi)什么不同了。如下圖所示：

（這圖完全是自己用微軟自帶的畫(huà)圖工具畫(huà)的，不太好看，但是不影響理解，哈哈~）
理解了題意，現(xiàn)在來(lái)寫(xiě)解法。
這道題有兩種解法，第一種是使用額外空間的解法，比較簡(jiǎn)單；另一種是不使用額外空間的解法，寫(xiě)法比較奇妙，但是比較難寫(xiě)；
現(xiàn)在先講第一種使用額外空間的寫(xiě)法。用額外空間呢，就是使用一個(gè)Map。
首先遍歷一遍鏈表，將鏈表中所有節(jié)點(diǎn)都在Map中存儲(chǔ)下來(lái)。哦，對(duì)了，map就是<key,value>類型的一種結(jié)構(gòu)，如果不了解的同學(xué)，請(qǐng)自行百度，網(wǎng)上很多關(guān)于map的介紹。
代碼如下：

cur = pHead;
while(cur != NULL){
    map.insert(pair<RanomListNode*, RandomListNode*>(cur, new RandomListNode(cur->value));
    cur = cur->next;
}

這只是一個(gè)代碼片段，里面出現(xiàn)的東西，下面會(huì)有完整介紹。
此時(shí)，我在map中已經(jīng)存有和現(xiàn)有鏈表一樣多的節(jié)點(diǎn)了，并且節(jié)點(diǎn)值也是一樣的。只是，我們還沒(méi)有設(shè)置map中節(jié)點(diǎn)的next指針和random指針，換言之，這時(shí)map中的所有節(jié)點(diǎn)是斷開(kāi)的。
如下圖：

很明顯，我們知道接下來(lái)要做什么。就是將這些節(jié)點(diǎn)按照題目給出的鏈表模樣串起來(lái)。
其次，將拷貝節(jié)點(diǎn)按照原鏈表連接好它們的next指針和random指針。
那么怎么串呢？我們看一下上面兩張圖，1的next指針連的是2，因此我們的拷貝節(jié)點(diǎn)1'就得連2'。也就是說(shuō)，我們需要通過(guò)map去找到節(jié)點(diǎn)1的拷貝節(jié)點(diǎn)1‘，然后通過(guò)map去找到1的下一個(gè)節(jié)點(diǎn)的拷貝節(jié)點(diǎn)2'。這不是很好理解，通過(guò)代碼展示什么意思：

myMap[cur]->next = myMap[cur->next];

根據(jù)代碼來(lái)看，我們通過(guò)myMap[cur]找到cur的拷貝節(jié)點(diǎn)，這個(gè)拷貝節(jié)點(diǎn)的next指針指向了cur節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的拷貝節(jié)點(diǎn)。這樣，就把兩個(gè)拷貝節(jié)點(diǎn)連接起來(lái)了。
random指針同理設(shè)置。
代碼如下：

myMap[cur]->random = myMap[cur->random];

最后一步，返回拷貝鏈表的頭節(jié)點(diǎn)。因?yàn)?，此時(shí)拷貝節(jié)點(diǎn)都串起來(lái)了，形成了完整的鏈表，只要返回鏈表頭部，就能得到整個(gè)拷貝鏈表了。到此，所有步驟就已經(jīng)結(jié)束了。
下面是完整代碼：

#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];
    }
};

運(yùn)行結(jié)果：

測(cè)試代碼就自己寫(xiě)一下吧，比較簡(jiǎn)單。這種寫(xiě)法的關(guān)鍵是要掌握map的使用，別的也沒(méi)有什么了。

至于不用額外空間的寫(xiě)法，那就更逆天了，下次再寫(xiě)吧，哈哈~

感謝各位大佬的閱讀。歡迎評(píng)論，歡迎點(diǎn)贊~

================================================================================================================
如果可以的話，打個(gè)賞也行啊，哈哈~
一毛兩毛也表示萬(wàn)分感謝，哈哈~

                                                 下面是我的支付寶及微信二維碼