Создание стека из кругового связанного списка, чтобы распечатать список обратно

Question

im решение некоторых вещей для практики для моего теста. Вопрос в моем учебнике предлагает мне напечатать материал в круговом связанном списке. поэтому моя идея состояла в том, чтобы создать стек, переместить материал в стек и затем поместить его.

Вот что я сделал:

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>).

Если список двусвязный:

Start от последнего элемента в списке (если не хранить ссылку на хвост перебирать узлы до последнего не будет достигнут) и просмотр списка с помощью 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(); 
}