给出一个链表，每个节点包含一个额外增加的随机指针可以指向链表中的任何节点或空的节点。
返回一个深拷贝的链表。
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 两个能打都没有。
