CareerCup

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:

void printListInReverse(Node* head) {
  if (head != NULL) {
    printListInReverse(head->next);
    cout << head->data;
  }
}

Which is basically the first solution but using the stack frame for the function calls instead of a stack for the node values.

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.

You should reverse list, change reference in all items that next item should contain reference to previos. After that you can print all list in reverse order

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());
	}