# [138\. Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/)

:::spoiler Solution

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

class Solution {
private:
    unordered_map<Node*, Node*> oldToNew;
public:
    Node* copyRandomList(Node* head)
    {
        return dfs(head);
    }

    Node* dfs(Node* node)
    {
        if (!node) return nullptr;
        if (oldToNew.count(node)) return oldToNew[node];
        
        // 如果沒有找到 node
        oldToNew[node] = new Node(node->val);
        oldToNew[node]->next = dfs(node->next);
        oldToNew[node]->random = dfs(node->random);
        return oldToNew[node];
    }
};

- 時間複雜度：$O(N)$
- 空間複雜度：$O(N)$
:::