0

im solving some stuff for practice for my test. The question in my text book asks me to print the stuff in the circular linked list reversely. so my idea was to create a stack, move the stuff to the stack and then pop it.

Here is what i've done:

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

My problem is i cannot use do. I need a different solution instead. Any help?

4

2 回答 2

1

如果您“被允许”使用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();
}
于 2013-05-11T09:09:01.813 回答
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);
}

这很简单，但效率不高。如果列表包含太多元素，您甚至可能会遇到递归深度太深的问题。

*编辑：固定终止条件

于 2013-05-11T08:46:36.003 回答