Copy List with Random Pointer Leetcode

題目會給我們一個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]