LeetCode Solutions
138. Copy List with Random Pointer
Time: $O(n)$ Space: $O(n)$
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == nullptr)
return nullptr;
if (map.count(head))
return map[head];
Node* newNode = new Node(head->val);
map[head] = newNode;
newNode->next = copyRandomList(head->next);
newNode->random = copyRandomList(head->random);
return newNode;
}
private:
unordered_map<Node*, Node*> map;
};
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<Node, Node> map = new HashMap<>();
}
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 = {}