# LeetCode Medium 138. Copy List with Random Pointer

tags: leetcode

問題

• Explore
• Problems

アイデア

｢ランダムな位置のノードを指すポインタを持つ単方向連結リストをdeep copyせよ，つまり完全にコピーせよ｣という問題です．

やるだけですね(出来なかった並感)．

解法

連想配列を使ってコピーします．

• 最初に全てのノードをコピーします．
• 次に，全てのノードのnextとrandomをコピーします．

非常に簡単なのに気付けなかった…どうかしている．

計算量

ノードの数を$N$とします．

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(N)$

Python

"""
# 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: 'Node') -> 'Node':
        if not head:
            return head
        
        node_hash = {}
        node = head
        while node:
            node_hash[node] = Node(node.val, None, None)
            node = node.next
        
        node = head
        for key in node_hash:
            if key.next:
                node_hash[key].next = node_hash[key.next]
            if key.random:
                node_hash[key].random = node_hash[key.random]
            node = node.next
            
        return node_hash[head]