題目會給我們一個Node的鍵結，該鍵結上每個Node都有兩個指向，一個是Next一個是Random，我們要複製這個鍵結一份再回傳。
第一種做法
一開始最直覺的做法，我是先跑一次node，紀錄整個鏈結的狀態後再複製一份。
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if head is None:
return None
nodeValList = []
nodeRandomIndexList = []
newNodeList = []
while head is not None:
nodeValList.append(head.val)
randomNode = head.random if head is not None else None
if randomNode is None:
nodeRandomIndexList.append(None)
else:
distance2End = 0
while randomNode is not None:
randomNode = randomNode.next
distance2End+=1
nodeRandomIndexList.append(distance2End)
head = head.next
for val in nodeValList:
newNodeList.append(Node(val))
for (idx, node), distance2End in zip(enumerate(newNodeList),nodeRandomIndexList):
if idx == len(newNodeList)-1:
node.next = None
else:
node.next = newNodeList[idx+1]
if distance2End is None:
continue
else:
node.random = newNodeList[len(nodeValList)-distance2End]
return newNodeList[0]第二種做法
將Node當成鍵值創建字典，並且新建對應的新結點。
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if head is None:
return None
nodeDict = {}
newNodeList = []
#
while head is not None:
newNode = Node(head.val,head.next,head.random)
nodeDict[head] = newNode
newNodeList.append(newNode)
#
head = head.next
#
for node in newNodeList:
if node.next is not None:
node.next = nodeDict[node.next]
if node.random is not None:
node.random = nodeDict[node.random]
return newNodeList[0]
