以相反順序打印鏈表的遞歸方法

Question

我在編寫應接受對通用單鏈表的引用並創建測試程序以在字符串列表上測試我的方法的方法時遇到問題（打印列出有序和倒序）。我已經創建了一個稱爲SinglyLinkedList的單鏈表。

Answer 1

按順序，在調用函數之前調用輸出方法。

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); 
}