Print LinkedList in reverse order

This question is easy but if it is not understood properly we end up writing code to reverse the underlying linked list.

Here we just need to print the linked list in reverse order, not to reverse it. So simple recursion will do the magic.

if (head == null) return; 

reverseLinkedList(head.nextNode); 

System.out.print( head.data + " "); 

Yes, that’s right. just 3 line code will print any linkedlist in reverse order. Lets put it in a java method and see how it works.

package in.questionsforinterview.problems;

public class Tester {

	/* Code to reverse the linked list */
	void printReverseOrder(Node head) {
		if (head == null)
			return;

		// print list of head node
		printReverseOrder(head.nextLink);

		// print data here
		System.out.print(head.data + " ");
	}

	///////////////////////////////////////////////////////////////////////////////////////////////
	// Boiler plate utility code to create a linkedlist and add some data
	///////////////////////////////////////////////////////////////////////////////////////////////

	Node head; // head of list

	/* Linked list Node */
	class Node {
		int data;
		Node nextLink;

		Node(int d) {
			data = d;
			nextLink = null;
		}
	}

	/* Inserts a new Node at front of the list. */
	public void push(int data) {

		Node node = new Node(data);

		/* add new Node at the end of the list */

		if (head == null) {
			head = node;
			return;
		}

		Node temp = head;
		while (temp.nextLink != null) {
			temp = temp.nextLink;
		}

		temp.nextLink = node;
	}

	public void printNaturalOrder() {

		Node temp = head;

		while (temp != null) {
			System.out.print(temp.data + " ");
			temp = temp.nextLink;
		}

	}

	/* Drier function to test the above methods */
	public static void main(String args[]) {

//		Let us create linked list 
		Tester llist = new Tester();
//		Add few nodes 5->6->7->8
		llist.push(5);
		llist.push(6);
		llist.push(7);
		llist.push(8);

		System.out.println("Insert Order: ");
		// pass the head node
		llist.printNaturalOrder();

		System.out.println("\nReverse Order: ");
		// pass the head node
		llist.printReverseOrder(llist.head);
	}

}

Output

Insert Order: 
5 6 7 8 
Reverse Order: 
8 7 6 5 

Explanation:

  1. First the flow starts when the printReverseOrder(Node node) method is called with head node from main().
  2. Now the if condition checks whether the passed head node is null This condition is called Base condition
  3. if node is not null then it’ll call the printReverseOrder() again with the next node – Recursion call 1
  4. Step 2 & 3 will be performed until the last node where the node points to null Recursion call 4
  5. In our example we have only 4 nodes, so at 4th recursion call our null check will be true, Once the condition is true then our recursion flow ends there with return statement.
  6. As we know that so far it did not execute statements after the recursion method call printReverseOrder(). Now as the base condition is met, it’ll execute statements after the recursion call for each step (i.e Recursion call 1 – 4 ) in the reverse order or last in first out order.

Note: Recursion uses Stack data structure to store the method call order with the state (i.e variables, parameters data), So for each recursion call it’ll push the data related to the call to an internal Stack. When the base condition returns it’ll pop each entry from the stack and execute rest of the statements with the data snapshot stored in the stack.

For ex. if you’ve passed node 5 in the first recursion call, then it’ll print 5 when method call entry popped from the stack, since the data state was stored in the stack.

7. Now it’ll print head.data value from the stack which is the exact method argument passed while it is called. So for each pop from the stack it’ll print respective node value.

Finally if you pass a list of

1 -> 2 -> 3 -> 4 -> 5

The output will be

5 4 3 2 1

Note : we are not reversing underlying linkedlist, we are just leveraging the recursion to print the linked list in reverse order.

Thanks for reading it through, if you enjoyed the article or wants to make suggestions please let me know in the comments.