🐙

NeetCode 150 [Linked List] medium : Copy List With Random Pointer

2025/04/11に公開

 NeetCodeのSolutionを書いていく
 Copy List With Random Pointer
 問題長さ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)

 例

Input: head = [[3,null],[7,3],[4,0],[5,1]]

Output: [[3,null],[7,3],[4,0],[5,1]]


Input: head = [[1,null],[2,2],[3,2]]

Output: [[1,null],[2,2],[3,2]]

 メモポイントは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

NeetCodeのSolutionを書いていく

Copy List With Random Pointer

問題

制約

例

メモ

Discussion