6

リンクリストは 2 つのポインターで与えられます。1 つ目は次のノードを指すもので、もう 1 つはランダムポインターです。ランダム ポインターは、LinkedList の任意のノードを指しています。元のリストを変更せずに O(n) で Linked List(c,c++,c#) のコピーを作成する完全なプログラムを作成します。

あるインタビューでこの質問をされたのですが、答えがわかりませんでした。助けていただければ幸いです。

4

5 に答える 5

17

通常のリンクされたリストを線形時間でコピーすることは明らかに簡単です。これを興味深いものにしている唯一の部分は、「ランダムな」ポインターです。おそらく「ランダム」とは、同じリンクリスト内でランダムに選択された別のノードを指すことを意味します。おそらく、その意図は、リンクされたリストのコピーがまったく同じ構造を再作成することです-つまり、「次の」ポインターは線形リストを作成し、他のポインターは同じ相対ノードを参照します(たとえば、ランダムポインター元のリストの最初のノードが元のリストの 5 番目のノードを指している場合、重複リストのランダム ポインターも重複リストの 5 番目のノードを指します。

これを N 2時間で行うのはかなり簡単です。まず、ランダム ポインターを無視して、通常どおりにリストを複製します。次に、元のリストを一度に 1 ノードずつ調べ、各ノードについて再びリストを調べて、ランダム ポインターが参照したリストのノードを見つけます (つまり、ポインターを保持しているnextポインターを見つけるためにポインターを介してトラバースするノードの数)現在のノードnextのポインタと同じアドレスrandom. 次に、重複リストを調べて、それを逆にします.N番目のノードのアドレスを見つけて、それを現在のノードのランダムポインタに入れます.

これが O(N 2 ) である理由は、主に正しいノードの線形検索です。O(N) を取得するには、線形の複雑さではなく、一定の複雑さでこれらの検索を実行する必要があります。

これを行うための明白な方法は、元のリスト内の各ノードのアドレスをリスト内のそのノードの位置にマッピングするハッシュ テーブルを作成することです。次に、新しいリスト内のノードのアドレスを保持する配列を作成できます。

これらを使用すると、ランダム ポインターを修正するのは非常に簡単です。最初に、ポインターを介して元のリストをnextたどり、ノードを複製し、ポインターを介して接続された新しいリストを作成しnextますが、ランダムポインターはそのままにします。その際、各ノードのアドレスと位置をハッシュ テーブルに挿入し、新しいリストの各ノードのアドレスを配列に挿入します。

それが終わったら、古いリストと新しいリストを順を追って見ていきます。古いリストの各ノードについて、そのノードのランダム ポインターのアドレスを確認します。ハッシュ テーブルでそのアドレスに関連付けられた位置を検索し、その位置にある新しいリストのノードのアドレスを取得し、それを新しいリストの現在のノードのランダム ポインターに入れます。次に、古いリストと新しいリストの両方で次のノードに進みます。

完了したら、ハッシュ テーブルと配列の両方を破棄/破棄します。これは、新しいリストが古いリストの構造を複製するようになり、余分なデータはもう必要ないためです。

于 2012-07-16T03:39:37.193 に答える
7

編集を明確にする：

BowieOwensが指摘したように、以下は「ランダムな」ポインタが一意である場合にのみ機能します。
一般的なアイデアのためだけに答えを残していますが、それは間違いなく間違っているので、賛成しないでください。

私が完全に間違っていなければ、追加のストレージを使用せずにこれを行うことができます。

古いリストをコピーしているのでrandom、古いノードからのrandomポインタを新しいノードのポインタに保存します。
次に、random古いノードのポインタが新しいノードを指すように設定します。

これにより、古いリストと新しいリストの間に「ジグザグ」構造ができます。

擬似コード:

Node* old_node = <whatever>;
Node * new_node = new Node;
new_node->random = old_node->random;
old_node->random = new_node;

そのように古いリストをコピーしたら、最初からやり直しますが、次のようにポインターを置き換え、新しいリストのポインターを対応する新しいノードにrandom設定しながら、古いリストのポインターを復元します。random

Node* old_random = old_node->random->random; // old list -> new list -> old list
Node* new_random = new_node->random->random; // new list -> old list -> new list
old_node->random = old_random;
new_node->random = new_random;

紙の上ではずっと良く見えますが、残念ながら私の ASCII アートのスキルでは十分ではありません。

これにより元のリストは変更されますが、元の状態に復元されます。
それが許されるかどうかは、面接次第だと思います。

于 2012-07-16T12:37:27.500 に答える
0

ご存じのとおり、O(n) は線形を意味します。線形データ構造のコピーが必要な場合、元のリストのノードを反復処理するだけでよく、訪問したノードごとに新しいリストの新しいノードを作成するだけなので、問題はありません。仕事をするためにいくつかの側面を知る必要があるため、質問はうまく定式化されていないと思います:これは循環的な実装ですか? 「次の」ノードは何ですか? ノードの次のノードまたはリストの最初のノード? リストはどのように終了しますか？

于 2012-07-16T02:56:19.357 に答える
-1

たぶん、この質問は、非常に単純なので、奇妙な質問にどのように答えるかをテストするためのトリックです。

1) 各ノードに繰り返す

2) 他のリンク リストの新しいノードを作成し、値をコピーします。

コストは常に O(n) です。リンクされたリスト全体を 1 回だけ反復するだけだからです !!!

または、彼の質問のどこかが間違っていることを理解しています。

于 2012-07-16T03:16:41.363 に答える