CareerCup

You could do an iterative reversal of the linked list, and then print the reversed linked list in a loop. Then, reverse the list again before you return in order to restore the original state of the list.

This approach requires you to modify the list. You won't be able to do that if the list is immutable, or if other threads might be reading the list at the same time as you execute this algorithm.

Reversing a linked list and printing it out once it's reversed both take O(n) time, so the algorithm is O(n) time overall. The space used (in addition to the space occupied by the input) is O(1) as reversal can be implemented iteratively in O(1) space, and so can printing each node.

Push value of each node to a stack as you traverse the list. At the end of the list, pop values in the stack and print them.

Push each node into the stack till end of the list in a while loop.
Pop each element from the stack and print till stack empty.

usage of stack is same as recursion.isn't it ? both will increase the memory complexity..Just looking for an optimized solution..

def reverse(curr, prev):
  while (curr):
    next=curr.next
    curr.next=prev
    prev=curr
    curr=next
  return prev

def print(head):
  while(head):
    print head.val

def reverse_print(head):
  head=reverse(head, None)
  print(head)
  reverse(head, None)

1. reverse iteratively and then print
2. put into stack and print the elements by popping the element from the stack

If it is just a matter of printing the elements in reverse order, we can do the following:

String s = new String();
Node n = head;
while (n != null) {
   s = new String(n.data) + ", " + s;
   n = n.next;
}

Apart from usage of stack as mentioned by srini above, I feel you can use below approach as well:

void print (list *n)
{
if (n != NULL)
print(n->next);

printf("%d", n->data);
}

1234567890