Leetcode 138 Solution

This article provides solution to leetcode question 138 (copy-list-with-random-pointer)
Categories:
Tags:
Access this page by simply typing in "lcs 138" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/copy-list-with-random-pointer

Solution

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""



class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        m = {}



        def copy(node):
            if node is None:
                return None



            if node in m:
                return m[node]



            new_node = Node(node.val)
            m[node] = new_node



            new_node.next = copy(node.next)
            new_node.random = copy(node.random)



            return new_node



        return copy(head)