給出一個(gè)鏈表筐骇，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針可以指向鏈表中的任何節(jié)點(diǎn)或空的節(jié)點(diǎn)槽片。
返回一個(gè)深拷貝的鏈表捞蚂。
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] #用來加速隨機(jī)部分賦值
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 兩個(gè)能打都沒有金赦。
