java - 循環単一リンクリストを逆に印刷する

Question

私は教科書からランダムに質問を練習していますが、この質問に出くわし、それを成し遂げることができませんでした.

循環単一リンクリストを逆順に印刷するにはどうすればよいですか? 例：リストに要素がある場合： 1 2 3 、それらを出力する必要があります 3 2 1

これは循環リンク リストであり、メソッドにパラメーターを含めないでください。

ありがとうございました！

Answer 1

基本ケース (開始ノードが次のノードと等しい) では、現在のノードを出力します。それ以外の場合は、次のノードで再帰し、現在のノードを出力します。

これはスタックのために線形スペースを使用することに注意してください。ただし、バック ポインターがないため、これが最適です。

Answer 2

どうですか：

class Node {
    int data;
    Node next;
    public Node getNode() ...
    public String toString() ...
}

public class CircularList {

    private Node list;

    public void printReverse() {
        final Node head = this.list;
        printReverseRecurse(list, head);
        System.out.println(list.toString());
    }

    private void printReverseRecurse(Node node, Node head) {
        if (node != head) {
            printReverseRecurse(node.getNext(), head);
            System.out.print(node.toString());
        }
    }
}

head編集後、プライベート メソッドへの参照を 渡すのを忘れていました。

Answer 3

プログラム スタックの代わりにヒープ上のスタックを使用する非再帰的なアプローチを次に示します。再帰的アプローチよりも少ないメモリを使用する必要があります。

class Node { 
    private int data;
    private Node next;
    public Node getNode() { ... }
    public String toString() { ... }
}

public class CircularList {

    private Node list;

    public reversePrint() {
        Stack<Node> stack = new Stack<Node>();

        // First, put all the entries in the stack
        Node node = list;
        do {
            stack.push(node);
            node = node.getNext();
        } while (node != list);

        while (!stack.empty()) {
            System.out.print(stack.pop());
        }
    }

}