复杂链表复制，简单的O(n), O(n)解法

提供一个不一样的解法，O(n), O(n), 这道题只要能找到random指针的映射关系即可，可以考虑使用字典保存这种映射关系。把所有节点放在一个list里面，然后计算random的映射字典(位置->位置)，然后复制一个新的list，依次赋值next和random

class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        p1 = pHead
        nodes = []
        d = {}
        while p1:
            nodes.append(p1)
            p1 = p1.next
        p1 = pHead
        while p1:
            if p1.random:
                d[nodes.index(p1)] = nodes.index(p1.random)
            else:
                d[nodes.index(p1)] = -1
            p1 = p1.next
        new_nodes = [RandomListNode(x.label) for x in nodes]
        for i, node in enumerate(new_nodes):
            if i < len(new_nodes)-1:
                node.next = new_nodes[i+1]

            if d[i] != -1:
                node.random = new_nodes[d[i]]

        return new_nodes[0] if new_nodes else None