[解決済み] ダブリーリンクリストの反転

質問

このメソッドは、n個の要素を持つ2重リンクリストを反転させるものです。このメソッドがどのように動作するのかがわかりません。コメントを追加しましたので、間違っていたら訂正してください。トラバース処理がどのように行われるのかがよくわからないのです。

 public void reverseDLL( ) {
   Node temp=head; //swap head and tail
   head=tail; // head now points to tail
   tail=temp; //tail points to head
    //traverse the list swapping prev and next fields of each node
  Node p=head; //create a node and point to head

  while(p!=null) //while p does not equal null
    { //swap prev and next of current node
      temp=p.next; // p.next does that not equal null? confusing.
      p.next=p.prev; //this line makes sense since you have to reverse the link
      p.prev=temp; //having trouble visualizing this.
      p=p.next;//advance current node which makes sense
    }
 }

解決方法は？

コードを数行ずつ見てみましょう。

Node temp=head;
head=tail;
tail=temp;

ここでは、いくつかの変数を設定しているだけです。頭部を尾部に、尾部を頭部にと入れ替えています。

ここで、開始ノードを定義します。これは新しい頭で、以前は尻尾でした。

Node p=head; //create a node and point to head

while(p!=null)
{ 
    temp=p.next; 

この時点では、こんな感じです（注：これが最初のイテレーションの場合。 next はNULLを指すことになりますが、それは問題ではなく、その場合はAをNULLと仮定すればよいのです)。

そこで、次のようになります。 next を指し、Aを指す prev を指している。これらを入れ替えたい。これを行うには、先に next を prev (Bを指している)ので、今は next と prev はともにBを指しています。

    p.next=p.prev; 

素晴らしい！あと半分です。今、私たちは

さて、最後のステップは prev は何を指すのか next を指していた。どうやってアクセスするのでしょうか？幸いなことに、私たちは next を指していた（言い換えればA）。 temp . では、それを使って prev .

    p.prev=temp; 

残念ですが、あります。

これでこのノードは交換されたので、次のノードに移ります。

    p=p.next;
}

繰り返してください。

みんなで一緒に

Node p=head; //create a node and point to head

while(p!=null)
{ 
    temp=p.next; 
    p.next=p.prev; 
    p.prev=temp; 
    p=p.next;
}