Print single linked list in a reverse order (java / example / recursive)

• Given a single linked list, print single linked list in reverse order in java.
• Traverse the single linked list using recursive algorithm.

Example: reverse single linked list using recursive algorithm

• The regular order printing of above linked list is:
  • 1 2 3 4 5
• Print single linked list in reverse order i.e. starting from node 5 (from last node) till the head node.
  • 5 4 3 2 1

 

Algorithm – print single linked list in reverse order using recursion

• Recursive function taking head reference of linked list
• Keep on calling the recursive function
  • We will use tail recursion method.
  • Until we reach last node of linked list
  • We have reached the last node
  • return from here (so that we start printing the data)
• Start printing the data (As we have reached last node)
  • Stack unwinding, will print the data from last to first node.

Time complexity of algorithm is O (n)

Program – print single linked list in reverse order using recursive algorithm.

1.) PrintReverseLinkedList Class:

• PrintReverseLinkedList class is responsible for printing single linked list in reverse order.
• We will traverse single linked list using recursive method.

package org.learn.Question;

import org.learn.List.Node;

public class PrintReverseLinkedList {
	public static void printReverseLinkedList(Node head) {
		if (null == head) {
			return;
		}
		printReverseLinkedList(head.next);
		System.out.printf("%d ", head.data);
	}

	public static void insert(Node head, int data) {
		while (head.next != null)
			head = head.next;
		head.next = new Node(data);
	}

	public static void print(Node head) {
		while (head != null) {
			System.out.printf("%d ", head.data);
			head = head.next;
		}
		System.out.println("");
	}
}

2.) App Class:

We are performing the following operation in main method

• We are creating the single linked list in main method.
• We will call method of PrintReverseLinkedList class, to print single linked list, in a reverse order.

package org.learn.Client;

import org.learn.List.Node;
import org.learn.Question.PrintReverseLinkedList;

public class App {
	public static void main(String[] args) {
		int[] data = { 1, 2, 3, 4, 5 };
		Node head = new Node(data[0]);

		for (int count = 1; count < data.length; count++)
			PrintReverseLinkedList.insert(head, data[count]);

		System.out.println("1. Original Single linked list : ");
		PrintReverseLinkedList.print(head);

		System.out.println("2. Printing single linked list in reverse order : ");
		PrintReverseLinkedList.printReverseLinkedList(head);
	}
}

3.) Node Class:

• Node class is representing the node (s) of a single linked list

package org.learn.List;

public class Node {
	public int data;
	public Node next;

	public Node(int num) {
		this.data = num;
		this.next = null;
	}
}

Output – print single linked list in reverse order using recursive algorithm

1. Original Single linked list : 
1 2 3 4 5 
2. Printing single linked list in reverse order : 
5 4 3 2 1 

Download code – print single linked list in reverse order