[LeetCode] 138. Copy List with Random Pointer

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

Use dictionary to map the original node to its copy.

Recursive 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: 'Node') -> 'Node':
        copies = {}
        
        def copy(node):
            if not node:
                return None
            
            copied = None
            if node in copies:
                return copies[node]
           
            copied = Node(node.val)
            copies[node] = copied
                
            copied.next = copy(node.next)
            copied.random = copy(node.random)
            
            return copied
        
        return copy(head)

Iterative solution:

Step1, create copy of each node and save the mapping relationship from each node to its copies.

Step2,  re-link each node's random pointer

"""
# 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):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        
        copies = dict()
        
        dummy = Node(0)
        
        p1 = dummy
        p2 = head
        
        while p2:
            p1.next = Node(p2.val)
            copies[p2] = p1.next
            
            p1 = p1.next
            p2 = p2.next
            
        
        p1 = dummy.next
        p2 = head
        while p1:
            if p2.random:
                p1.random = copies[p2.random]
                
            p1 = p1.next
            p2 = p2.next
            
        
        return dummy.next