# Definition for singly-linked list with a random pointer.

 # class RandomListNode:

 #     def __init__(self, x):

 #         self.label = x

 #         self.next = None

 #         self.random = None

 class Solution:

     # @param head, a RandomListNode

     # @return a RandomListNode

     def copyRandomList(self, head):

         if head is None:

             return head

         # insert newnode between every two nodes between oldlist

         p = head

         while p is not None:

             newnode = RandomListNode(p.label)

             tmp = p.next

             p.next = newnode

             newnode.next = tmp

             p = tmp

         # copy random point

         p = head

         while p is not None:

             if p.random is not None:

                 p.next.random = p.random.next

             p = p.next.next

         # extract the new list from mixed list

         newhead = head.next

         p = head

         while p is not None:

             tmp = p.next

             p.next = p.next.next

             p = p.next

             if tmp.next:

                 tmp.next = tmp.next.next

             tmp = tmp.next

         return newhead