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