105. 复制带随机指针的链表

给出一个链表，每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。
返回一个深拷贝的链表。
2017.11.16

"""
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):
        # write your code here
        labelList = []
        nodeList = []
        nodeMap = {}
        next = head
        i = 0
        while next != None:
            nodeList.append(RandomListNode(next.label))
            nodeMap[next.label] = nodeList[-1]   #用来加速随机部分赋值
            if i > 0:
                nodeList[i-1].next = nodeList[i]
            i += 1
            if next.random:
                labelList.append(next.random.label)
            else:
                labelList.append(next.random)
            next = next.next
        for i in range(len(labelList)):
            if labelList[i]:  # == None
                nodeList[i].random = nodeMap[labelList[i]]
            else:
                continue
        # for i in range(len(nodeList)-1):
        #     nodeList[i].next = nodeList[i+1]
        return nodeList[0]
                    
        

2017.11.17 两个能打都没有。