LeetCode-Python-138. ランダムポインタ付きチェーンテーブルのコピー

1641 ワード

チェーンテーブルが与えられ、各ノードは、チェーンテーブル内の任意のノードまたは空のノードを指すことができる追加のランダムポインタを含む.
このチェーンテーブルの深いコピーを返すように要求します. 
 
例:
入力:{“$id”:“1”,“next”:{“$id”:“2”,“next”:null,“random”:{“$ref”:“2”},“val”:2},“random”:{“$ref”:“2”},“val”:1}
説明:ノード1の値は1で、次のポインタとランダムポインタはノード2を指します.ノード2の値は2で、次のポインタはnullを指し、ランダムなポインタはそれ自身を指します. 
ヒント:
クローンリストへの参照として、指定されたヘッダのコピーを返さなければなりません.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/copy-list-with-random-pointer著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
考え方:
Emmm、最初に見ると133ではないでしょうか.
本題は133変種題で,133は図に隣接し,138はチェーンテーブルにランダムポインタがある点で異なる.
ハッシュテーブルmappingを開き、keyは古いノード、valは新しいノードです.
そして、古いノードのnextとrandomに対応する新しいノード(mapping[key.next]とmapping[key.random])を、新しいノード(val)のnext(val.next)とrandom(val.random)にそれぞれ付与する.
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random
"""
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        #133   ,      
        mapping = dict()
        
        p = head
        while p:
            mapping[p] = Node(p.val, None, None)
            p = p.next
            
        for key, val in mapping.items(): #key    , val    
            if key.next:
                val.next = mapping[key.next]
            if key.random and key.random in mapping:
                val.random = mapping[key.random]
            
        return mapping[head] if head else head