連結清單問題06：複制含有随機指針節點的連結清單

【題目】

一種特殊的連結清單節點類描述如下：

class  Node{
    public: 
        int value;
        Node *next;
        Node *rand;
        Node(int data) : value(data), next(NULL), rand(NULL){
        }
}
           

Node類中的value時節點值，next指針和正常單連結清單中next指針的意義一樣，都指向下一個節點，rand指針是Node類中新增的指針，這個指針可以指向連結清單的任意一個節點，也可以指向NULL。

給定一個由Node節點類型組成的無環單連結清單的頭節點head，請實作一個函數完成這個連結清單中所有結構的複制，并傳回複制的新連結清單的頭節點。

【解法1】

普通解法可以做到時間複雜度為O(N)，額外空間複雜度為O(N)，需要使用到哈希表（HashMap）結構。

（1）從左到右周遊連結清單，對每個節點都複制生成相應的副本節點，然後将對應關系放入哈希表map中。例如，連結清單 1 -> 2 -> 3 -> null，周遊1、2、3時依次生成1‘、2’、3‘，最後将對應關系放入map中。

key	value	意義
1	1’	表示節點1複制了節點1‘
2	2’	表示節點2複制了節點2‘
3	3’	表示節點3複制了節點3‘

步驟1完成後，原連結清單沒有任何改變，每一個副本節點的next和rand指針都指向null。

（2）再從左到右周遊連結清單，此時就可以設定每一個副本節點的next和rand指針。例如：原連結清單1 -> 2 -> 3 -> null，假設1的rand指針指向3，2的rand指針指向null，3的rand指針指向1。周遊到節點1時，可以從map中得到節點1的副本節點1’，節點1的next指向節點2，是以從map中得到節點2的副本節點2‘，然後令1’->next = 2'，副本節點1‘的next指針就設定好了。同時節點1的rand指向節點3，是以從map中得到節點3的副本節點3’，然後令1‘->rand = 3'，副本節點1’的rand指針也設定好了。以這種方式可以設定每一個副本節點的next和rand指針。

（3）将1‘節點作為結果傳回即可。

哈希表增删改查的操作時間複雜度都是O(1)，該方法一共隻周遊連結清單兩遍，是以普通解法的時間複雜度為O(N)，而空間複雜度為O(N)。

【解法1代碼實作】 

Node *copyListWithRand(Node *head)
{
     map<Node*, Node*> mapNode;
     Node *cur = head;
     while (cur != nullptr){
         mapNode.insert(pair<Node*, Node*>(cur, new Node(cur->value)));
         cur = cur -> next;
     }
     cur = head;
     while (cur != nullptr){
         mapNode[cur] -> next = mapNode[cur->next];
         mapNode[cur] -> rand = mapNode[cur->rand];
         cur = cur -> next;
     }
     return mapNode[head];
}
           

【解法2】

（1）從左到右周遊連結清單，對每個節點cur都複制生成相應的副本節點copy，然後把copy放在cur和下一個要周遊節點的中間。

例如：原連結清單為1->2->3->null，在步驟1完成後，原連結清單變成1->1'->2->2'->3->3'->null。

（2）再從左到右周遊連結清單，在周遊時設定每一個副本節點的rand指針。

例如：此時連結清單為1->1'->2->2'->3->3'->null，假設1的rand指針指向3，2的rand指針指向null，3的rand指針指向1。周遊到節點1時，節點1的下一個節點1->next就是副本節點1’。1的rand指針指向3，是以1‘的rand指針應該指向3’。如何找到3‘呢？因為每個節點的副本節點都在自己的後一個，是以此時通過3->next就可以找到3'，令1'->rand = 1'->rand->next即可。以這種方式可以設定每一個副本節點的rand指針。

（3）步驟2完成後，節點1，2，3，……之間的rand關系沒有發生任何變化，節點1‘，2‘，3’，……之間的rand關系也被正确設定了，此時所有的節點與副本節點串在一起，将其分離開來即可。

（4）将1‘節點作為結果傳回即可。

【解法2代碼實作】

Node *copyListWithRand(Node *head)
{
 if (pHead == nullptr){
    return nullptr;
 }
     Node *cur = head;
     Node *next = nullptr;
     //複制并連接配接每一個節點
     while (cur != nullptr){
         next = cur -> next;
         cur -> next = new Node(cur->value);
         cur -> next -> next = next;
         cur = next;
     }
     cur = head;
     Node *curCopy = nullptr;
     //設定複制節點的rand指針
     while (cur != nullptr){
         next = cur -> next -> next;
         curCopy = cur -> next;
         curCopy -> rand = cur -> rand != nullptr ? cur -> rand -> next : nullptr;
         cur = next;          
     }
     Node *res = head -> next;
     cur = head;
     //拆分
     while (cur != nullptr){
         next = cur -> next -> next;
         curCopy = cur -> next;
         cur -> next = next;
         curCopy -> next = next != nullptr ? next -> next : nullptr;
         cur = next;
     }
     return res;
    
}