同じ注文を維持するリンクリストのディープコピーを作成する方法

Question

私が把握できなかった就職の面接で、次の質問をしました。

class Node { 
    int value; 
    Node next; // points to next element in list 
    Node random; // points to one random element of list 
} 

は、あなたがこれらのノード（20のノードと言う）次の要素に「次」のポイントと他のものに「ランダム」のポイントのリンクリストを持って言う：あなたは、次のノード要素のリンクリストを与えています（つまり、リスト内の特定であるがランダムに選択された要素の1つを指すことができる）。つまり、第1要素の「ランダム」はノード＃5を指し、ノード第2要素のランダム点はノード＃9を指します。

質問：新しいリンクリストを作成するにはどうすればよいですか？このノードのリストは、 "ランダム"と "次の"の両方に対して同じ順序と同じリンケージを維持しますか？

つまり、これらの2つのポインタのいずれかを使用してこの新しいリストをトラバースすると、トラバーサルの順序は同じになります。

他のトピックでは、デフォルトのクローンを介して同じポインタをクローンしていますが、それはこの問題に対処できません。

Answer 1

オンラインでしばらく検索したところ、私はこの問題を答えで見つけました。かなりトリッキー。

• コピーのすべてのノード、すなわち、新しく作成されたすべてのノード
• ブレーク2

のリストについては、

コピーランダムポインタをすべてのノードを複製し、それをリストに挿入します。彼らは、この主要な解決策を提示します

こちらを参照してください：すべてのノードhttp://www.programcreek.com/2012/12/leetcode-copy-list-with-random-pointer/

Answer 2

ループと値としてキーと新しいノードのインスタンスとしてノードでHashMapにすべてのノードを置きます。

Map<Node, Node> nodeMap = new HashMap<>(); 
... 
nodeMap.put(currentNode, new Node(); 

今、あなたは再びちょうどnode.nextを通じて、あなたがあなたの代わりに、古いノード自体をマップの値を参照しているノードは、そのようなコピーのノードごとにループすることにより、すべてのあなたの「古い」ノードを反復処理。

その後、重複したインスタンスを含まない正確なコピーが必要です。また

Answer 3

、より多くのソリューションのためにこれらのリンクをチェック：

Method 1

Method 2

Method 3

参考：ArrayListのクローンを作成しても、そのクローンを作成する[方法のgeeksforgeeks