“Write a function which will print values from the single linked list in the reverse order in O(n) time. No changes to the list can be made and no additional data structures can be used”



This sounds like a challenging problem, as we can’t do any modifications to the list and as we reach the last node there is no way of going in opposite direction. However, if we think about the problem the only thing is needed is to push all values into the stack while we traverse the list and then just print values out of the stack. While we are not allowed to use additional data structures same effect can be achieved by using recursion. 


Possible solution:  



public void PrintInReverseOrder (Node head) { if (head != null) { PrintInReverseOrder(head.next); Console.WriteLine(head.value); }; }






Answers and Comments