從圓形鏈表創建一個堆棧，以便反向打印列表

Question

即時解決一些實踐的東西，爲我的測試。我的課本中的問題要求我反向打印圓形鏈表中的內容。所以我的想法是創建一個堆棧，將這些東西移動到堆棧然後彈出。

這裏是我做了什麼：

public void reversePrint() { 
    Stack stack = new Stack(); 

    Node<E> temp = list; 
    do { 
    stack.push(temp); 
    temp = temp.getNext(); 
    } while (temp != list); 

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

circularlist.java

public class CircularList<E> implements List<E> { 

    Node<E> list; 
    int size; 

    public CircularList() { 
    list = new Node(null); 
    list.setNext(list); 
    size = 0; 
    } 

    @Override 
    public void add(E element) { 
    Node<E> newNode = new Node(element); 
    newNode.setNext(list.getNext()); 
    list.setNext(newNode); 
    size++; 
    } 

    @Override 
    public boolean remove(E element) { 
    Node<E> location = find(element); 
    if (location != null) { 
     location.setNext(location.getNext().getNext()); 
     size--; 
    } 
    return location != null; 
    } 

    @Override 
    public E get(E element) { 
    Node<E> location = find(element); 
    if (location != null) { 
     return (E) location.getNext().getInfo(); 
    } 
    return null; 
    } 

    @Override 
    public boolean contains(E element) { 
    return find(element) != null; 
    } 

    @Override 
    public int size() { 
    return size; 
    } 

    @Override 
    public Iterator<E> iterator() { 
    return new Iterator<E>() { 
     Node<E> tmp = list.getNext(); 

     @Override 
     public boolean hasNext() { 
     return tmp != list; 
     } 

     @Override 
     public E next() { 
     E info = tmp.getInfo(); 
     tmp = tmp.getNext(); 
     return info; 
     } 

     @Override 
     public void remove() { 
     throw new UnsupportedOperationException("Not supported yet."); 
     } 
    }; 
    } 

    protected Node<E> find(E element) { 
    Node<E> tmp = list; 
    while (tmp.getNext() != list && !tmp.getNext().getInfo().equals(element)) { 
     tmp = tmp.getNext(); 
    } 

    if (tmp.getNext() == list) { 
     return null; 
    } else { 
     return tmp; 
    } 

}

Node.java

public class Node<E> { 

    E info; 
    Node<E> next; 

    public Node(E element) { 
    info = element; 
    next = null; 
    } 

    public void setInfo(E element) { 
    info = element; 
    } 

    public E getInfo() { 
    return info; 
    } 

    public void setNext(Node<E> next) { 
    this.next = next; 
    } 

    public Node<E> getNext() { 
    return next; 
    } 
} 

我的問題是我不能使用做。我需要一個不同的解決方案。任何幫助？

Answer 1

我假設你有自己寫的LinkedList（使用Node<T>類）。

如果列表雙向鏈表：

開始從最後一個元素列表中（如果你不存儲到尾的引用遍歷的節點到達最後一個，直到），並遍歷使用getPrevious()列表（不管getNext()的名字相反）。

如果該列表是單鏈表：

而不是使用堆棧的，你可以遞歸遍歷列表，打印時展開的元素。

public static void <T> reverse(Node<T> current, Node<T> stopAt) { 
    Node<T> next = current.getNext(); 
    if (next != stopAt) { 
     reverse(next); 
    } 
    System.out.println(next.getValue(), stopAt); 
} 

這很簡單，但並非真正有效。如果列表中包含太多元素，則可能會遇到遞歸深度過深的問題。

*編輯：固定的終止條件

Answer 2

如果你在「允許」使用while循環，你可以轉換你的do環路成，使用break出去：

while (true) { 
    stack.push(temp); 
    temp = temp.getNext(); 
    // If we're back to the beginning, we're done 
    if (temp == list) { 
     break; 
    } 
} 

或者如果你可以使用size，它更容易：

Node<E> temp = list; 
for (int i = 0; i < size; i++) { 
    stack.push(temp); 
    temp = temp.getNext(); 
}