역순으로 순환 연결된 목록 인쇄

Question

나는 내 교과서에서 무작위로 질문을하고 있는데이 질문을 검토하고 끝내지 못했습니다.

어떻게 순환적인 단일 링크 목록을 역순으로 인쇄 할 수 있습니까? 예 : 목록에 요소가있는 경우 : 1 2 3, 인쇄해야 함 3 2 1

참고 : 순환 연결된 목록이므로 메서드에 매개 변수가 없어야합니다.

감사합니다.

Answer 1

기본 경우 (시작 노드가 다음 노드와 같음)에서 현재 노드를 인쇄하십시오. 그렇지 않으면 다음 노드에서 재귀를 수행 한 다음 현재 노드를 인쇄하십시오.

참고 이것은 스택 때문에 선형 공간을 사용합니다. 그러나 이것은 백 포인터가 없기 때문에 최적입니다. 편집 후

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 2

.

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