class Solution(object):
    def copyRandomList(self, head):
        if not head:
            return head

        pos = {}
        pos[None] = None

        #映射  
        p = head
        while p:
            pos[p] = ListNode(p.val)
            p = p.next

        #复制
        p = head
        while p:
            pos[p].next = pos[p.next]
            pos[p].random = pos[p.random]
            p = p.next

        return pos[head]