138. 複制帶随機指針的連結清單 力扣（中等） 哈希+連結清單

題目描述：

給你一個長度為 n 的連結清單，每個節點包含一個額外增加的随機指針 random ，該指針可以指向連結清單中的任何節點或空節點。

構造這個連結清單的 深拷貝。 深拷貝應該正好由 n 個 全新 節點組成，其中每個新節點的值都設為其對應的原節點的值。新節點的 next 指針和 random 指針也都應指向複制連結清單中的新節點，并使原連結清單和複制連結清單中的這些指針能夠表示相同的連結清單狀态。複制連結清單中的指針都不應指向原連結清單中的節點 。

例如，如果原連結清單中有 X 和 Y 兩個節點，其中 X.random --> Y 。那麼在複制連結清單中對應的兩個節點 x 和 y ，同樣有 x.random --> y 。

傳回複制連結清單的頭節點。

用一個由 n 個節點組成的連結清單來表示輸入/輸出中的連結清單。每個節點用一個 [val, random_index] 表示：

val：一個表示 Node.val 的整數。

random_index：随機指針指向的節點索引（範圍從 0 到 n-1）；如果不指向任何節點，則為  null 。

你的代碼 隻 接受原連結清單的頭節點 head 作為傳入參數。

示例 1：

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

題源：https://leetcode-cn.com/problems/copy-list-with-random-pointer/

題解： 就是完全複制一個一模一樣的連結清單，但是和原來的連結清單沒有節點重複

• Node(val)           建立的是一個節點，不是指針；
• new Node(val)     是一個指向這個節點的指針。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
    
    if(head==NULL)  return NULL;

    map<Node*,Node*> mp;
    Node* head2= new Node(head->val);  // Node* head2=Node(head->val) 錯誤
    Node* cur1=head;
    Node* cur2=head2;
    
    while(cur1!=NULL)
    {
        mp[cur1]=cur2;   //  建構映射，也就是hash
        if(cur1->next==NULL) break;
        cur2->next=new Node(cur1->next->val);  // 需要 new在前面
        cur1=cur1->next;
        cur2=cur2->next;
    }
    cur1=head;
    cur2=head2;
    while(cur1!=NULL)
    {
        if(cur1->random==NULL) cur2->random = NULL;
            else cur2->random=mp[cur1->random];
        cur1=cur1->next;
        cur2=cur2->next;
    }
    return head2;
    }
};