LeetCode 138. ランダムポインタ付きチェーンテーブルのコピー(Java)
4940 ワード
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著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
考え方:遡及/再帰
チェーンテーブルが与えられ、各ノードは、チェーンテーブル内の任意のノードまたは空のノードを指すことができる追加のランダムポインタを含む.このチェーンテーブルの深いコピーを返すように要求します.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;
}
}