How to read a singly linked list backwards?

Question

One method which I can think of is to reverse the list and then read it. But this involves changing the list which is bad.
OR I can make a copy of the list and then reverse it, but this uses additional O(n) memory. Is there any better method which doesn't use extra memory and doesn't modify the list and runs in O(n) time

reverse linked list code is something like this in c#

Void Reverse (Node head)
{
    Node prev= null;
    Node current = head;
    Node nextNode = null;

        while (current!=null)
        {
            nextNode = current.Next;
            current.Next = prev;
            prev=current;
            current = nextNode; 

        }
        head = prev;

}   

Recursive solution is

void ReadBackWard (Node n)
{
    if (n==null)
        return;
    else
        ReadBackward(n.Next);

    Console.WriteLine(n.Data);

}

Answer 1

There is a third solution, this time using O(log(n)) memory and O(n log(n)) time, thus occupying the middle ground between the two solutions in Marc's answer.

It is effectively a reverse in-order descent of a binary tree [O(log(n))], except at each step you need to find the top of the tree [O(n)]:

1. Split the list in two
2. Recurse into the second half of the list
3. Print the value at the midpoint
4. Recurse into the first half

Here is the solution in Python (I don't know C#):

def findMidpoint(head, tail):
  pos, mid = head, head
  while pos is not tail and pos.next is not tail:
    pos, mid = pos.next.next, mid.next
  return mid

def printReversed(head, tail=None):
  if head is not tail:
    mid = findMidpoint(head, tail)
    printReversed(mid.next, tail)
    print mid.value,
    printReversed(head, mid)

This could be recast using iteration instead of recursion, but at the cost of clarity.

For example, for a million-entry list, the three solutions take on the order of:

Solution   Memory       Performance
=========================================
 Marc #1     4MB    1 million operations
  Mine       80B    20 million operations
 Marc #2      4B    1 trillion operations

Answer 2

One of the hallmarks of a singly-linked list is that it is, in fact, singly linked. It is a one-way street, and there's no way to overcome that unless you turn it into something else (such as a reversed singly-linked list, a stack, a doubly-linked list...). One must be true to the nature of things.

As has been pointed out earlier; if you need to traverse a list both ways; you need to have a doubly-linked list. That is the nature of a doubly linked list, it goes both ways.