java - 反向打印循环单链表

Question

我正在解决一些练习题，但我无法正确解决。问题要求我反向打印列表，它不应该带任何参数，只调用 printReverse() 并反向打印列表。我想到了堆栈方式，这里是:

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

  public void reversePrinter() {

    Stack stack = new Stack();
    Node<E> temp = list;

    for (int i = 0; i < size; i++) {
        stack.push(temp.getInfo());
        temp = temp.getNext();
      }

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

节点.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;
  }
}

主.java

public class Main {

  public static void main(String[] args) {
    CircularList<String> x = new CircularList<String>();

    x.add("hi");
    x.add("hhhh");
    x.add("hi");
    x.add("hhhh");
    x.add("hi");
    x.reversePrinter();


  }
}

这会打印: hhhh 嗨 hhhh 嗨 null

它应该打印: 嗨嗨嗨嗨嗨

请帮我解决。谢谢!

Answer 1

考虑更换循环:

for (int i = 0; i < size; i++) {
    stack.push(temp.getInfo());
    temp = temp.getNext();
  }

使用您的迭代器进行以下操作:

for (Node<E> n : this) {
    stack.push(n);
}

等价于:

public void reversePrinter() {
    Stack stack = new Stack();        //create a stack for reversing order
    Iterator<E> it = this.iterator(); //get this object's iterator
    while(it.hasNext())               //while there is still another object
      stack.push(it.next());          //add the next object to the stack

    while(!stack.empty())             //while the stack is not empty
      System.out.print(stack.pop());  //print the data from the stack
}

假设您的迭代器已正确实现，这应该可以工作