copy_list_with_random_pointer
1from typing import Optional 2 3 4# @leet start 5 6 7class Node: 8 def __init__(self, x: int, next=None, random=None): 9 self.val = int(x) 10 self.next = next 11 self.random = random 12 13 14class Solution: 15 def copyRandomList(self, head: Optional[Node]) -> Optional[Node]: 16 """ 17 This question asks to copy a list where the nodes have a random pointer, 18 which can point to anywhere in the list. 19 20 Given this constraint, we have to copy the list. We can treat this as if 21 it was a graph, and try to clone it, where have a visited set to count 22 for cycles. 23 24 We copy each node by making a new instance of the passed in node given 25 a value, and maintaining a cache with a new copy of the list. 26 27 We then make sure to copy the random and next pointers for every value 28 in the list by returning `traverse(node.random)` and `traverse(node.next)` 29 before returning our copied node. 30 """ 31 visited = {} 32 33 def traverse(node): 34 if not node: 35 return None 36 if node in visited: 37 return visited[node] 38 copy = Node(node.val) 39 visited[node] = copy 40 41 copy.random = traverse(node.random) 42 copy.next = traverse(node.next) 43 return copy 44 45 return traverse(head) 46 47 48# @leet end 49 50 51def test(): 52 assert 2 + 2 == 4
class
Node:
8class Node: 9 def __init__(self, x: int, next=None, random=None): 10 self.val = int(x) 11 self.next = next 12 self.random = random
class
Solution:
15class Solution: 16 def copyRandomList(self, head: Optional[Node]) -> Optional[Node]: 17 """ 18 This question asks to copy a list where the nodes have a random pointer, 19 which can point to anywhere in the list. 20 21 Given this constraint, we have to copy the list. We can treat this as if 22 it was a graph, and try to clone it, where have a visited set to count 23 for cycles. 24 25 We copy each node by making a new instance of the passed in node given 26 a value, and maintaining a cache with a new copy of the list. 27 28 We then make sure to copy the random and next pointers for every value 29 in the list by returning `traverse(node.random)` and `traverse(node.next)` 30 before returning our copied node. 31 """ 32 visited = {} 33 34 def traverse(node): 35 if not node: 36 return None 37 if node in visited: 38 return visited[node] 39 copy = Node(node.val) 40 visited[node] = copy 41 42 copy.random = traverse(node.random) 43 copy.next = traverse(node.next) 44 return copy 45 46 return traverse(head)
16 def copyRandomList(self, head: Optional[Node]) -> Optional[Node]: 17 """ 18 This question asks to copy a list where the nodes have a random pointer, 19 which can point to anywhere in the list. 20 21 Given this constraint, we have to copy the list. We can treat this as if 22 it was a graph, and try to clone it, where have a visited set to count 23 for cycles. 24 25 We copy each node by making a new instance of the passed in node given 26 a value, and maintaining a cache with a new copy of the list. 27 28 We then make sure to copy the random and next pointers for every value 29 in the list by returning `traverse(node.random)` and `traverse(node.next)` 30 before returning our copied node. 31 """ 32 visited = {} 33 34 def traverse(node): 35 if not node: 36 return None 37 if node in visited: 38 return visited[node] 39 copy = Node(node.val) 40 visited[node] = copy 41 42 copy.random = traverse(node.random) 43 copy.next = traverse(node.next) 44 return copy 45 46 return traverse(head)
This question asks to copy a list where the nodes have a random pointer, which can point to anywhere in the list.
Given this constraint, we have to copy the list. We can treat this as if it was a graph, and try to clone it, where have a visited set to count for cycles.
We copy each node by making a new instance of the passed in node given a value, and maintaining a cache with a new copy of the list.
We then make sure to copy the random and next pointers for every value
in the list by returning traverse(node.random) and traverse(node.next)
before returning our copied node.
def
test():