int LinkedList::DoStuff()
{
Node *Current = next_;
while ( Current != NULL )
{
Current = Current->next_;
length_++;
}
// At the last iteration we have reached the end/tail/last node
return length_;
}
最後を超えるノードはありません。どうすればテールエンドからフロントヘッドまでトラバースできますか？
リンクリストが二重リンクリストでない限り、これを行うのは困難です。再帰は1つの方法であり、スタックスペースが不足するほど大きなリストがないと仮定すると、次のようになります（擬似コード）。
DoStuffBackwards (currNode) {
if (currNode != NULL) {
DoStuffBackwards (currNode->next);
// Process currNode here.
}
}
DoStuffBackwards (firstNode);
これが機能するDoStuffBackwards()のは、リストがなくなるまで次のノードを呼び出し続け、その後、再帰スタックをロールバックするときに、各ノードを処理するためです。
最後のノードから現在のノードに戻りたいだけの場合は、Pax の答え (再帰を使用) が最善の策です。以下の私のバージョンも参照してください。現在のノードが非循環単一リンク リストの先頭でなく、現在のノードから先頭ノードに移動したい場合、それは不可能です。
int LinkedList::DoStuff()
{
return DoStuffBackward(next_, 0);
}
int LinkedList::DoStuffBackward(Node* node, int n)
{
if (!node)
{
return n;
}
int len = DoStuffBackward(node->next_, n + 1);
std::cout << "doing stuff for node " << n << std::endl;
return len;
}
これは宿題の匂いがするのでコードはありませんが、再帰を必要としないソリューションの概要を次に示します。
リストを逆方向に実行したい場合は、最後を見つけるためにトラバースするときにリストを再リンクして逆方向を指すオプションが 1 つあります。次に、リストを再トラバースすると (元のリストとは逆の順序でノードにアクセスします)、以前と同じように再リンクを繰り返すと、リストは元の順序で終了します。
これは概念的には単純ですが、ポインターとリンクを正しく処理する (特にリストの最初と最後で) のは少し難しい場合があります。
リンクリストクラスは二重リンクですか、それとも単一リンクですか？各ノード内に前のポインターがない場合、逆方向にトラバースすることはできません。
また、より多くのコードを投稿し、時間をかけて質問を読みやすくすることをお勧めします。
元のリストの各要素に対して 1 つのエントリを持つ配列などの補助データ構造を構築できるように、再帰が機能します。O(n) の余分なストレージを必要としないシングルスレッド リストのソリューションが必要な場合は、Michael が提案するようにリストを元に戻すことをお勧めします。この例を書きましたが、[宿題の心配があるので省略します]。リストを反転する際の注意点: 元のリストへのポインターを保持する他のデータ構造があり、トラバーサル中にそれらにアクセスする可能性がある場合、リストが反転している間にリストにアクセスする必要がある場合、それらは機能しません。リストを変更しようとすると、データが破損する可能性があります。
更新: わかりました。リストを元に戻す (C++) ルーチンを次に示します。ただし、テストされていません。これが宿題である場合、投稿者は完全な答えを得るためにこのルーチンを正しく使用する方法を理解する必要があることに注意してください。
Node *ReverseList(Node *head) {
// Reverse a single-threaded list in place, return new head
Node *prev=NULL;
Node *cur=head;
while (Node *next=cur->next_) {
cur->next_ = prev;
prev = cur;
cur = next;
}
cur->next_ = prev;
return cur;
}
リストをスタックにプッシュしてからポップします。