6

すぐ下のこのメソッドは、n 個の要素を持つ双方向リンク リストを逆にします。これが実際にどのように機能するのかわかりません。コメントを追加しました。間違っている場合は修正してください。トラバースプロセスがどのように機能するかわかりません。

 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
    }
 }
4

8 に答える 8

26

一度に数行ずつコードをステップ実行してみましょう。

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

ここでは、いくつかの変数を設定しています。尾を指すように頭を交換し、頭を尾に向けます。

次に、開始ノードを定義します。これは尻尾だった新しい頭です。

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

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

この時点で、これが私たちが見ているものです (注: これが最初の反復である場合、nextnull を指しますが、それは問題ではありません。その場合は A が null であると想定してください): ここに画像の説明を入力

つまりnext、A をprev指し、B を指しています。これらを交換したいのです。そうするために、先に進んで(B を指している) に割り当てるのでnext、両方ともB を指します。prevnextprev

    p.next=p.prev;

すごい！道半ばです。これで、次のようになりました。

ステップ2

最後のステップは、以前は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;
}
于 2012-06-23T05:33:28.910 に答える
2

これがお役に立てば幸いです。

struct node* current = head;
struct node* next;
struct node* prev = NULL;



while (current != NULL)  //traverse the whole linked list 
{
   next  = current->next;  //temporarily store the next node
   current->next = prev;    //now assign the prev!node to next of current node
   prev = current;   //update the previous pointer
   current = next;  //update the current pointer

}

この図を見てください。 ここに画像の説明を入力

あなたがそれを得る願っています。

ありがとう

于 2012-06-23T05:01:01.837 に答える
1

リストのすべての要素で、前のポインターと次のポインターを交換するだけです。だからあなたのコメントは正しいです。新しいヘッドの次のポインターは null として開始されます。そして、その前のポインターにコピーされます。リストの先頭であるため、その prev はもちろん null にする必要があります。

Vj シャーの答えは、コードが異なるだけで同じことを行います。

于 2012-06-23T05:11:57.130 に答える
1

簡単にするために、ヘッドノードから開始することもできます。それ以外の場合、アルゴリズムは同じままです。

Node currentNode=head;

while(currentNode!=null){
    Node temp = currentNode.next;
    currentNode.next=currentNode.prev;
    currentNode.prev=temp;
    currentNode=currentNode.prev;
}
于 2016-07-06T14:10:16.273 に答える
0

この反転がどのように機能するかの鍵は、単純な二重連結リストが反転される前と後でどのように見えるかを見ることです。リストを逆にするために何が必要かがわかれば、その方法は理解しやすくなります。

Nodes最初のノードが 0 の次のようなものがあるとします。

node       0    1    2    3    4
data       A    L    I    S    T
next       1    2    3    4   null
prev      null  0    1    2    3

上記のノードを 0 から順にトラバースすると、次の出力が得られます。

各ノードのデータをそのままにしておくと、各ノードの前のノードと次のノードの値を交換することで、リストを逆にすることができます。

node       0    1    2    3    4
data       A    L    I    S    T
next      null  0    1    2    3
prev       1    2    3    4   null

上記のノードを 4 から順にトラバースすると、次の出力が得られます。TSILA

これを行うためのコードは、Node クラス自体があると仮定すると簡単です。

public class Node {
    private char ch;
    private Node next;
    private Node prev;
}

public static Node reverse(Node trav) {
    Node swapped;
        while (trav != null) {
            swapped.next = trav.prev;
            swapped.prev = trav.next;
            trav = swap;
            trav = trav.prev;  // it was swapped so you need to follow prev
            }
        return trav  // return the new head node
}
于 2013-10-29T23:06:35.173 に答える