誰かが頭部ノードを与えられた二重リンクリストの逆転を私に説明することはできますか？

Question

私は他の解決策を検討しましたが、効果を視覚化するのに苦労しました。 私たちは.nextと.prevを切り替える必要があることを理解しかし、私たちは、たとえばので

を.prevするために反復されている理由を理解していない： 考えるとヌル---> A - > < - B ---> < --- C ---> <、-D - >ヌル

ヘッドが

は、我々が設定されている場合は、変数

トラバースしばらく頭に "トラバース"！ = Null ...

1）TEMP =

2）traverse.prev = traverse.next

3）traverse.next = TEMP

4）（混乱部）**トラバース= traverse.prev traverse.prev？

だから、私たちの与えられた設定では、最初の反復の後に、それは...

Bだろう - > < -A- - > NULL、C ---> < ---> D-- - > Null

これを考えると、私は2回目の反復を視覚化することはできません。また、Bが横切れば、CとAを入れ替えることになりますか？

Answer 1

は、元のリストのプロセスの次のノードはnextためtraverse.prevによって今指し示され、prevが交換されました。最初の反復後A.next

はnullとA.prevあるBを指しているが、B.prevは依然としてCを指しているAとB.nextを指しています。

B.prevがCを指し、B.nextがAを指している。

したがって、各インターレーションで、単一のノードの参照を修正し、元のリストの次のものに移動します（現在はprevのターゲットに設定されています）。

Answer 2

あなたがAの次へ前へ/を入れ替えているが、Bに触れていないので、Bはまだ

A<--B-->C 

でなければならないとあなたはBを指しますので、私は次の反復は、あなたが交換すると思いますbのprev/nextポインタ、次にcに移動する（スイッチの後にb.prevになる）...あなたが完了したら、新しい頭（D）になる "traverse" 。

有効なリストでnode.next.prevは最後のものを除くすべてのオブジェクトのノードでなければならないので、リストは乱されます（無効）.2番目の反復の後では、A.nextはnullになります。 A.prev.prevは正しいものではありません。

リストが無効であるため、シンプルなアスキー表記を使用して可視化することはできません。node.next.prev = nodeは常に保持されているものとみなします。

A有効な表記は次のようになります。

初期：

Null<--A-->B A<--B-->C B<--C-->D C<--D-->Null 
    ^
    Traverse 

最初ieration後：この新しい表記法を使用して

B<--A-->Null A<--B-->C B<--C-->D C<--D-->Null 
      ^ ^
      ^ Traverse 
      ^
     Temporarily 
     invalid. 

、もう一度それを試してみてください。

また、私はそれを「ながら」状態末尾に移動して行うことになります。

While (traverse.prev != null) 

あなたはまだあなたが呼び出し元に戻ることができ、どの（新しいヘッドを指し示す横断するポインタを保持している。この方法を）、そうでなければあなたが持っているものは、今はあまり面白くないテール（元の頭）へのポインタです。

うわー、私は持っていなければならないよりも、その答えにもっと多くの努力を費やしました - しかし、私はデータ構造が大好きです。ステップ1、2と3後

Answer 3

ダブルリンクリスト

NULL<-A<=>B<=>C<=>D->NULL 

そして、あなたのアルゴリズムを考える

traverse = A 

while traverse != Null... 
    temp   = traverse.prev // [1] 
    traverse.prev = traverse.next // [2] 
    traverse.next = temp    // [3] 
    traverse  = traverse.prev // [4] 

ライン[1]、[2]と[3]スワップ前のトラバースの次のノード。あなたのチェーンがあるだけで四行目の前に、のは、それはあなたの最初の繰り返しだとしましょう：あなたの四行目が実行されたとき

 +----------+ 
     |   | A.prev 
     |   V 
(traverse = A) <-- B <=> C <=> D -> NULL 
     | 
     | A.next 
     v 
     NULL 

ので、traverseはBを意味し、あなたが移動するA.prevになります。