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