NeetCodeのSolutionを書いていく #
Copy List With Random Pointer #
https://neetcode.io/problems/copy-linked-list-with-random-pointer
neetcode.io
問題 #
長さnのリンクリストの先頭を与えられます。 片方向リストとは異なり、ランダムリンクを持ちます。 ランダムリンクはどのノードにもリンクでき、あるいはnullにリンクします。
Listのdeep copyを作りなさい。
deep copyはn個の新しいnodeで構成され、それぞれ以下の特性を持ちます。
- オリジナルの値valを持ちます
- nextのnodeはオリジナルと同じです
- randomのnodeはオリジナルと同じです
全ての新しいリストは古いnodeに接続してはいけません。
制約 #
- nは0以上100以下
- 値は-100以上100以下
- randomはnullかリンクリスト内のノードのどれか
計算時間：O(n) メモリ：O(n)
例 #
メモ #
ポイントはrandomが指し示す先を正しく管理するところ。 特にrandomが次の方を指定している場合、deep copyされる新しいnodeはまだないので、指定することができない。 例えば、例1で7のdeep copyを作ったタイミングで5のdeep copyはまだないので参照できない。
当然全nodeのdeep copyを作ってから改めて繋げば問題はない。 しかしこの場合もどれを繋げばよいかはわからないか。 つまり、deep copyされた7の次にdeep copyされた5をつなぎたいが、5がどこにあるかは不明。 更にはvalはユニークではないので探すこともできない。
以下3つのループで行けるか？
- オリジナルデータをループし、dict[original_node, index]のようなノードに対するノード番号を記録しておく
- 新しいデータを作る。この時、dict[index, new_node]のようなノード番号に対するノードを記録しておく
- 最後にオリジナルデータをループし、各ノードがrandomで参照するノードを取得する
- original_node -> index -> new_nodeのように新しいデータのrandomに紐づけるnodeが明るので紐づける
from typing import Optional
# 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]":
# オリジナルデータをループし、dict[original_node, index]のようなノードに対するノード番号を記録しておく
node = head
indexes: dict[Node, int] = {}
index = 0
while node:
indexes[node] = index
index += 1
node = node.next
# 新しいデータを作る。この時、dict[index, new_node]のようなノード番号に対するノードを記録しておく
# この時点ではrandomは全てNone
dummy = Node(0)
new_node = dummy
node = head
nodes: dict[int, Node] = {}
index = 0
while node:
new_node.next = Node(node.val)
node = node.next
new_node = new_node.next
nodes[index] = new_node
index += 1
new_node = dummy.next
# 最後にオリジナルデータをループし、各ノードがrandomで参照するノードを取得する
node = head
while node:
index = None if node.random is None else indexes[node.random]
new_node.random = None if index is None else nodes[index]
node = node.next
new_node = new_node.next
return dummy.next