Printing a singly linked list in reverse order

Question

I am preparing for interview and I want to write the function in the way that the interviewers will expect me to write.

private static void printReverse(ListNode l1){
 if(l1 != null){
 printReverse(l1.next);
 System.out.print(l1.val + " ");
 }
 }

However, this function does not do anything if l1 is null. Should I take care of this case? If yes, how?

Answer 1

Even with such a short piece of code there is a lot to say.

Firstly, your example code is an example, designed to test just one piece of skill. A real list should never expose the fact that the implementation relies on a ListNode. In fact, your method is private, indicating that the detail is not public. The real printReverse method should have no argument, and should be public, because it should start with the head node of the list, and use that to start the recursive reverse print.

Also, that would be the right place to handle the nulls....

Recursive methods often (normally?) come in pairs, a setup method, and the actual recursive method. Your pair would look like:

public void printReverse() {
 if (head == null) {
 System.out.println("null");
 } else {
 printReverseRecursive(head);
 }
}
private void printReverseRecursive(ListNode node) {
 if (node == null) {
 return;
 }
 printReverseRecursive(node.next);
 System.out.print(node.val + " ");
}

Note, that while we are there, you have one of those wtf moments in your variable names. the name l1 is a really, really bad name. l is very easy to confuse with 1, and should never be used as a simple 1-letter variable name, and then, to make it worse, you put them together? Huh.

• Marco Acierno: And i would avoid recursion in cases like this due to the fact that the List can get veeeerrry large
• rolfl: @MarcoAcierno - I should have pointed that out in the post, that the stack limits the length of the list. But, without the recursion, reversing the list is much, much harder, and requires non-stack space... right?

Answer 2

Though less concise a iterative solution is more appropriate do to stack overflow (when the list is too long).

private void printReverse(ListNode node) { 
 Stack<ListNode> stack = new Stack<>();
 while(node != null) {
 stack.push(node);
 node = node.next;
 }
 while(!stack.empty())
 System.out.println(stack.pop());
}