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);
}
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…