java - 如何在 Java 中不使用递归打印反向链表？

Question

我尝试在没有递归的情况下打印反向链表并反转链表。我该怎么做？

问题:如何在不使用递归且不反转列表的情况下打印反向链表？

要求:没有多余的空格，不能反转链表，不能使用递归。

这里是链表节点的定义

class Node {
  int value;
  Node next;

  public Node(int val) {
    this.value = val;
  }
}

这是我的 printReverseLinkedList 的递归版本:

public void printReverseList(Node head) {
    Node temp = head;
    if (temp.next != null) {
        printReverseList(temp.next);
    }
    System.out.print(temp.value);
}

性能无所谓，因为我只想做成这样。

Answer 1

如果您既不能反转列表，也不能使用递归，那么唯一的方法是:

public void printReversList(Node head) {

    Node current = head; // used to search through the list
    Node last    = null; // stores the last element that we printed

    while (last != head) { // = we didn't print everything yet

        // find next element to print - it's one element before we reach "last"
        while (current.next != last) {
            current = current.next;
        }

        // Store the current element as the new last and print it
        last  = current;
        system.out.print(last.value);

        // reset current and start all over
        current = head;
    }
}

非常无效，但我想不出其他办法。