Interview Question
Country: India
Interview Type: In-Person
No offense to the interviewer but this question just sounds and feels dumb because the answer djmclaugh gave here is pretty much all we need here.
Recursive method without changing the list. It can even be done in iterative way.
public void printReverseLL(LinkedListNode<String> currentNode){
// check if the list is empty
if(currentNode == null){
return;
}
// If not the end of list, then call the same function with next node
printReverseLL(currentNode.getNext());
// Print the value before returning
System.out.print(currentNode.getValue());
}
You could push the values in a stack while going through the list in order and then print the values as you remove them from the stack: O(n) time and O(n) memory.
You could also keep track of the index of the last printed element and start from the beginning and traverse the list one less than that index until you print the first element: O(n^2) time and O(1) memory. I feel this is not a good solution though.
If you are allowed to alter the linked list as long as you restore it by the end of the algorithm, you can reverse the list (O(n) time O(1) memory), print it in order (O(n) time O(1) memory), and reverse it again (O(n) time O(1) memory) for a total of O(n) time and O(1) memory.
If you must use recursion, then you want something like this:
Which is basically the first solution but using the stack frame for the function calls instead of a stack for the node values.
- djmclaugh August 26, 2014