C++リンクリストの逆転 - ポインタが進まない

Question

リンクリストを逆にすることに関して質問がありますが、私は自分の実装でこれを理解しようとします。

私のコードは意味があり、うまくいくはずですが、デバッガを実行するとループは無限に実行されます。具体的には、headとnextはリンクされたリストの第1ノードと第2ノードの間を交互に保持します。 getLink()メソッドは、ノードのポインタ（リスト内の次のノードを指している）を返します。 whileループの下のコメントに基づいた入力は役に立ちます。

これはどのように

void revNodes(IntNodePtr& head) 
{ 
    IntNodePtr prev = NULL; 
    IntNodePtr next = NULL; 
    next = head; 
    while (next != NULL) 
    { 
     prev = head; 
     // this should advance the pointer head to the next node in the list because next is the same as head initially 
     head = next->getLink(); 
     // advance the pointer next to node after it 
     next = next->getLink(); 
     // set the pointer in the node that head is pointing to to prev (head before head was advanced) 
     head->setLink(prev); 
    } 
} 

Answer 1

。

効果的には、リストの先頭の後にある最初のノードを指しているので、そのノード上のポインタをリストの先頭に設定します（head->setLink(prev)）。したがって、ループを次回通過するときには、headとnextの両方が元のヘッドノードに戻ってきます！

を変更した場合：あなたは、リストをが、を進めることができるようになります

あなたがheadを設定すると、あなたは、次のノードをジャンプします：

next = next->getLink(); 

へnext->getLink()になります。最初にnextをhead->getLink()に初期化し、ループ内にhead〜nextと設定し、上記のようにnext〜head->getLink()と設定してください。

だから、コードにそれを回す：

void revNodes(IntNodePtr& head) 
{ 
    IntNodePtr prev = NULL; 
    IntNodePtr next = NULL; 
    next = head->getLink(); 
    while (next != NULL) 
    { 
     prev = head; 
     // this should advance the pointer head to the next node in the list 
     head = next; 
     // advance the pointer next to node after it 
     next = next->getLink(); 
     // set the pointer in the node that head is pointing to to prev (head before head was advanced) 
     head->setLink(prev); 
    } 
} 

Answer 2

：あなたはheadにnextを初期化して、ループ内であなたが同じノードに両方のポイントにそれらを設定している

void revNodes(IntNodePtr&head) 
{ 
    IntNodePtr prev = NULL; 
    IntNodePtr next = NULL; 
    IntNodePtr p = head; 
    while (p){ 
     next = p->getLink(); 
     p->setLink(prev); 
     prev = p; 
     p = next; 
    } 
    head = prev; 
} 

Answer 3

あなたのアルゴリズムには二つの問題があります。

1. リストの先頭の要素は逆リストの最後の要素になるだろう、あなたはそうはそのリンクをNULLに設定する必要があります。

2. ループの最初の反復で、2番目の項目のリンクを最初のものに変更しましたが、次の項目（この場合は3番目の要素）へのポインタを進めませんでした。