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 $O(n \log n)$ time. This can be found here
Can one do this better?
My question: Is there an algorithm with $O(1)$ space complexity and $O(n)$ time complexity that prints such a list in reverse order?
Please note that the definition of the problem excludes an algorithm that prints a list in reversed order in linear time with $O(1)$ space for node references while changing the references of the list:
The list is traversed form start to end and the references are reversed during this traversal: the reference from a node to its successor is overwritten by a reverence to its predecessot. If on arrives at the and of the list is straersed form the former end (which is now the start) to the former start (which is now the end) and the nodes are printed.
