copy list with random pointer

# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class (object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return None
        dummy = head
        m = {}
        while head:
            node = RandomListNode(head.label)
            m[head] = node
            head = head.next
        
        head = dummy
        while head:
            if head.next:
                m[head].next = m[head.next]
            head = head.next
        
        head = dummy
        while head:
            if head.random:
                m[head].random = m[head.random]
            head = head.next
        return m[dummy]
        

# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class (object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return None
        cur = head
        while cur:
            next = cur.next
            node = RandomListNode(cur.label)
            cur.next = node
            node.next = next
            cur = next
        
        cur = head
        while cur:
            rand = cur.random
            if rand:
                cur.next.rand = rand.next
            cur = cur.next.next
        
        cur = head.next
        while cur and cur.next:
            cur.next = cur.next.next
            cur = cur.next
        
        return head