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


138.ランダムポインタ付きチェーンテーブルのコピー
チェーンテーブルが与えられ、各ノードは、チェーンテーブル内の任意のノードまたは空のノードを指すことができる追加のランダムポインタを含む.このチェーンテーブルの深いコピーを返すように要求します.n個のノードからなるチェーンテーブルを用いて,入出力におけるチェーンテーブルを表す.各ノードは[val,random_index]で表される:val:Nodeを表す.valの整数.random_index:ランダムポインタが指すノードインデックス(0からn-1の範囲).ノードを指さない場合null.
例1:入力:head=[[7,null],[13,0],[11,4],[10,2],[1,0]]出力:[[7,null],[13,0],[11,4],[10,2],[1,0]]
ヒント:-1000<=Node.val <= 10000 Node.randomは空(null)またはチェーンテーブル内のノードを指します.ノード数は1000を超えません.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/copy-list-with-random-pointer著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
考え方:遡及/再帰
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    HashMap<Node,Node> visited=new HashMap<>();
    public Node copyRandomList(Node head) {
        if(head==null)
        {
            return null;
        }
        //                
        if(this.visited.containsKey(head))
        {
            return this.visited.get(head);
        }
        //          ,       ,          
        Node newNode=new Node(head.val,null,null);
        this.visited.put(head,newNode);
        //              
        newNode.next=this.copyRandomList(head.next);
        //                  
        newNode.random=this.copyRandomList(head.random);
        return newNode;
    }
}