java - 反向打印循环单链表

Question

我正在从我的教科书中随机练习问题，我遇到了这个问题并且无法完成。

如何以相反的顺序打印循环单链表？例如：如果列表有元素： 1 2 3 ，它应该打印它们 3 2 1

请注意，它是一个循环链表，方法中不应包含任何参数。

谢谢！

Answer 1

在基本情况下（开始节点等于下一个节点），打印当前节点。否则，在下一个节点上递归，然后打印当前节点。

请注意，由于堆栈，这使用了线性空间，但这是最佳的，因为您没有反向指针。

Answer 2

这是使用递归的可能解决方案，打印方法不接收任何参数：

public class ReversePrinter {

    private Node<?> head;
    private Node<?> current;
    private boolean first = true;

    public ReversePrinter(Node<?> head) {
        this.head = head;
        this.current = head;
    }

    public void printReverse() {

        if (current == null) {
            return;
        } else if (current == head) {
            if (!first) return;
            first = false;
        }

        Node<?> previous = current;
        current = current.getNext();
        printReverse();
        System.out.println(previous.getInfo());

    }

}

像这样使用它：

ReversePrinter printer = new ReversePrinter(nodeHeadOfList);
printer.printReverse();

对于问题中的示例，它将在控制台上打印：

3
2
1

Answer 3

怎么样：

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 4

这是一种使用堆上的堆栈而不是程序堆栈的非递归方法。应该比递归方法使用更少的内存。

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

}