print the nodes of an immutable single-linked list in reverse order

Assume you have a single-linked list of length n. The list is immutable. A node node has a method next and node.next() returns a reference to the successor of node. node.print() prints the value of node node or does some other stuff, such etails don't matter.

Is it possible to print the nodes of the list in reverse order in linear time using only a constant amount of space?

Details:

For the last element of a list next points to a special node named NIL that represents the end of a list. For NIL next() and print() are not defined.

The following simple pseudocode program prints the nodes in the order of the list. FIRST_NODE points to the first node of the list. Variable names that store references to nodes are prefixed by 'node_'.

node_current=FIRST_NODE
while node_current!=NIL
    node_current.print()
node_nurrent=node_current.next()

This algorithm calls of the medthod next n-times and there is one variable that can hold a reference to a node.

To print the k-th node of the list one can traverse the list from the start node to the k-th node in k steps. So to print the list in reverse order the following algorithm works

node_first=FIRST_NODE
node_last=NIL
while node_last!=node_first
    node_current=node_first  
    while node_current!=node_last:
        node_previous=node_current
        node_current=node_current.next()
    node_previous.print()
    node_last=node_previous

It needs about $\frac{n^2}{2}$ calls of method next and needs 4 variables that can hold a reference to a node: node_first (the first node of the list), node_last (the last node that was printed), node_current (the node that is currently investigated) , node_previous (the predecessor of node_current)

It can be shown that there are algorithms that need about $O(n^{\frac{1}{k}})$ space and $O(n)$ time for an arbitrary choosen k from {2,3,4,...} to print a single-linked list in reversed order. It is also possible to do this in $O(\log n)$ space and $

No, there is no such algorithm. This is proved in Theorem 2 of "Almost Optimal Hash Sequence Traversal" by Coppersmith and Jakobsson.

StackExchange Computer Science Q#68769, answer score: 3