リンクリストを逆順に出力する再帰的メソッド

Question

一般的な単一リンクリストへの参照を受け入れ、文字列のリストに対してメソッドをテストするためのテストプログラムを作成する方法を書くのに問題があります。順番と逆順の両方のリスト）。私はすでにSinglyLinkedListという単一リンクリストを作成しています。

Answer 1

順不同では、関数recurisvelyを呼び出す前に出力メソッドを呼び出します。

void print(Node n) 
{ 
    if (n != null) 
    { 
     System.out.println(n.value); 
     print(n.next); 
    } 
} 

逆の場合は、最初に関数を呼び出してください。

void print(Node n) 
{ 
    if (n != null) 
    {   
     print(n.next); 
     System.out.println(n.value); 
    } 
} 

Answer 2

再帰について考えると、繰り返し何かをやり直すつもりであることがわかります。この場合、ノードを何度も印刷したいのですが、毎回別のノードが必要です。

最初に印刷するノードは、リストの最後にする必要があります。それは私に優れた基本事実を示しています。

void printReverse(Node node) { 
    if(node.next != null) { // we recurse every time unless we're on the last one 
     printReverse(node.next); // this says "do this to the next node first" 
    } 
    System.out.println(node.data); // we'll print out our node now 
} 

あなたは

1,2,3,4-

を持っていた場合は、その中の1のノードに印刷呼びたい考えてみましょう。それから "私は次のノードを持って、それを印刷する"と言うだろう。 2ノードにも次のノードがあるので、ノード3に向かいます。ノード3はまだ次のノードを持っているため、印刷前にノード4に向かいます。ノード4は、次のノードを持たないので、それ自体を印刷しようとしている。次に、ノード3がどこで中止したかに戻る。ここで、ノード3は印刷して、ノード2が中断したところに戻ることができる。それは印刷され、ノード1が中止された場所に移動します。印刷してメイン機能に戻ります。

Answer 3

私は上記の回答に100％同意します。私の実装では、ヘルパークラスなしでは動作しませんでした。私の答えは、他の人がコンパイルエラーを受ける場合に備えて、上記の答えを展開することだけです。

public void printReverse() 
{ 
printReverse(head); 
} 

private void printReverse(GNode<T> node) 
{ 
    if (node.next != null) 
    { 
    printReverse(node.next); 
    } 
    System.out.println(node.data); 
}