138. 複制帶随機指針的連結清單 連結清單

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

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

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

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

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

map + dfs

/*
// 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:
    unordered_map <Node*, Node*> mp;

    Node* copyRandomList(Node* head) {
        if (!head) {
            return nullptr;
        }

        if (!mp.count(head)) {
            auto headNew = new Node(head->val);
            mp[head] = headNew;
            headNew->next = copyRandomList(head->next);
            headNew->random = copyRandomList(head->random);
        }

        return mp[head];
    }
};