復雜鏈表的復制（一道算法題）

這是一道算法題。想寫篇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的使用，別的也沒有什么了。

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

感謝各位大佬的閱讀。歡迎評論，歡迎點贊~

================================================================================================================
如果可以的話，打個賞也行啊，哈哈~
一毛兩毛也表示萬分感謝，哈哈~

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