#!/usr/bin/env python
#coding: utf-8

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

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.
"""

import os
import random

# Definition for singly-linked list with a random pointer.
class RandomListNode(object):
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if None == head:
            return None
        
        # put the new copied node next to it's original node,
        step_node = head
        while step_node != None:
            new_node = RandomListNode(step_node.label)
            new_node.next = step_node.next
            step_node.next = new_node
            step_node = new_node.next
        
        # copy random value
        step_node = head
        while step_node != None:
            target_node = step_node.next
            target_node.random = step_node.random
            step_node = target_node.next
        
        # delete origin node
        step_node, copied_node, result = head, head.next, head.next
        while step_node != None:
            step_node = copied_node.next
            copied_node.next = step_node.next
            copied_node = step_node.next

        return result



def printList(head):
    step_node = head
    while step_node:
        temp_random_node = step_node.random
        if temp_random_node:
            print(step_node.label, " random -> ", step_node.random.label)
        else:
            print(step_node.label, " random -> ", None)
        step_node = step_node.next

head = RandomListNode(0)
node_list = []
step_node = head
for i in range(1, 5):
    temp_node = RandomListNode(i)
    step_node.next = temp_node
    step_node = temp_node
    node_list.append(temp_node)

for temp_node in node_list:
    temp_node.random = node_list[random.randint(0, len(node_list)) - 1]

solution = Solution()
copied_list = solution.copyRandomList(head)
printList(copied_list)        


@@ -904,27 +904,32 @@
 p_node.label
+ * 10
 )%0D%0A
-
             
@@ -1220,32 +1220,58 @@
 step_node.random
+ and step_node.random.next
 %0D%0A            st
@@ -1413,36 +1413,38 @@
 %0D%0A        while 
-step
+copied
 _node != None:%0D%0A
@@ -1433,32 +1433,44 @@
 ed_node != None:
+            
 %0D%0A            st
@@ -1476,16 +1476,21 @@
 tep_node
+.next
  = copie
@@ -1521,31 +1521,45 @@
  copied_node
+ = step_node
 .next 
-=
+and
  step_node.n
@@ -1553,32 +1553,37 @@
 d step_node.next
+.next
 %0D%0A            co
@@ -1572,38 +1572,36 @@
 xt%0D%0A            
-copied
+step
 _node = step_nod
@@ -2047,9 +2047,10 @@
 (1, 
-5
+10
 ):%0D%0A
@@ -2282,16 +2282,64 @@
 - 1%5D%0D%0A%0D%0A
+printList(head)%0D%0A%0D%0Aprint('================')%0D%0A%0D%0A
 solution
@@ -2428,12 +2428,58 @@
         %0D%0A%0D%0A
+%0D%0Aprint('================')%0D%0AprintList(head)%0D%0A

update problem