How to print a reverse linked list without using recursion in Java?

Question

I try printing a reverse linked list without recursion and reversing the linked list. How can I do that?

Questions: How to print a reverse linked list without using recursion and not reversing the list?

Requirements: No extra space, cannot reverse a linked list, cannot use recursion.

Here is the definition of the linked list Node

class Node {
  int value;
  Node next;

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

Here is my recursion version of printReverseLinkedList:

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

Performace does not matter, because I just want to do in this way.

Answer 1

If you may neither reverse the list, nor use recursion, the only way to do this is this:

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

It is highly ineffective, but there is no other way I can think of.