java - 片方向リストの複製

Question

私は単独でリンクされたリストを持っています。通常の「次へ」ポインタとは別に、各ノードには、リストのランダム ノードを指すポインタ (ランダム ptr) がもう 1 つあります。そのようなリストのクローンを作成する方法は? （O（n ^ 2）未満）。

Javaを使用した提案や解決策はありますか?

Answer 1

これは、O(n) 時間と O(1) 空間での答えです。(ハッシュテーブルまたはアソシエーション マップを使用するソリューションには、O(n) スペースが必要です)。shg のリンクも、O(n) 時間と O(1) 空間でのソリューションです。

• リストをトラバースして、セルの数 n を数えます。
• サイズ nの配列tを作成します。各セルは 2 つのポインターaとで構成されbます。アルゴリズムの最後に、これがコピーになります。しかし、それは今のところではありません。
• 元のリストをトラバースします。元のリスト のk^thセルの場合:c
  • t[k].aへのポインタにし ましょうc
  • letc.nextをポインタにしますt[k](元のリストは一時的に破棄されます。後で復元します)。元のリストと の間でポインターをたどることができますt。
• c元のリストをトラバースし、セルごとc.next.bに へのポインタを置きますc.random.next。(c.nextは のセルでありt、 も同様ですc.random.next)。このようにb、セルのフィールドは、元のリストのポインターtの構造のコピーです。random
• 元のリストを復元しkますt[k].a.next。t[k+1].a.next
• tリンクされたリストを作成kしt[k].aますt[k+1]。

shg のリンクとは対照的に、このソリューションには、メモリ内にサイズ n の連続ブロックが必要になるという欠点があります。

Answer 2

次の 2 つの方法があります。

1) すべてのノードのアドレスをハッシュし、ランダム ポインタが指しているノードを保存します。(全体的な複雑さは になりますO(n)。)

2) 別の O(n) ソリューションは、リンクに示すようになります (余分なスペースは使用しません): http://www.geeksforgeeks.org/archives/1155

Answer 3

すべてのノードを順番に複製し、この最初のパスで、元の各ノードをその複製に関連付ける ID マップを作成できます。

次に、2 番目のパスを実行し、元のノードごとに関連付けられたランダム ノードを取得し、マップから対応するクローンを取得して、元のノードのクローンをランダム ノードのクローンに関連付けます。プロセス全体は依然として O(n) です。

Answer 4

リスト内の各ノードには、「次へ」と「ランダム」の 2 つの参照があります。「ランダム」は常に前のものを参照していると仮定します。double-linked listを取得します。一般性を失うことなく、二重連結リストの複製の手順をリストの複製に適用できます。このSOの回答を確認して、DLリストをどのように複製したかを確認してください。複雑さは O(n) である必要があります。