LeetCode-Python-138. ランダムポインタ付きチェーンテーブルのコピー
チェーンテーブルが与えられ、各ノードは、チェーンテーブル内の任意のノードまたは空のノードを指すことができる追加のランダムポインタを含む.
このチェーンテーブルの深いコピーを返すように要求します.
例:
入力:{“$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)にそれぞれ付与する.
このチェーンテーブルの深いコピーを返すように要求します.
例:
入力:{“$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