Copy List with Random Pointer
Intuition Traverse the list, saving the visited one to avoid cyclic loop. Approach A recursive function that Check if that node was visited, if it was, return visited. Create new node Saved new node in the visited (visited[curr] = new_node) Recursevily call the function to compute next and random Return the new_node Complexity Time complexity: O(n) Space complexity: O(n) Code """ # Definition for a Node. class Node: def __init__(self, x, next=None, random=None): self.val = int(x) self.next = next self.random = random """ class Solution(object): visited = {} def copyRandomList(self, head): """ :type head: Node :rtype: Node """ if not head: return None if head in self.visited: return self.visited[head] new_node = Node(head.val, None, None) self.visited[head] = new_node new_node.next = self.copyRandomList(head.next) new_node.random = self.copyRandomList(head.random) return new_node