# 138. Copy List with Random Pointer

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public: Node* copyRandomList(Node* head) { if (head == nullptr) return nullptr; if (const auto it = map.find(head); it != cend(map)) return it->second; Node* newNode = new Node(head->val); map[head] = newNode; newNode->next = copyRandomList(head->next); newNode->random = copyRandomList(head->random); return newNode; } private: unordered_map map; }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution { public Node copyRandomList(Node head) { if (head == null) return null; if (map.containsKey(head)) return map.get(head); Node newNode = new Node(head.val); map.put(head, newNode); newNode.next = copyRandomList(head.next); newNode.random = copyRandomList(head.random); return newNode; } private Map map = new HashMap<>(); } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution: def copyRandomList(self, head: 'Node') -> 'Node': if not head: return None if head in self.map: return self.map[head] newNode = Node(head.val) self.map[head] = newNode newNode.next = self.copyRandomList(head.next) newNode.random = self.copyRandomList(head.random) return newNode map = {}