反向打印一个圆形单链表

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

} 

Answer 4

下面是一个使用递归的可能解决方案，印刷方法不接受任何参数：

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