Reverse linked list using recursion in Java

Reverse linked list using recursion OR Reverse linked list recursively .

---

Let's see, how to Reverse a linked list recursively in Java

There are 2 ways to Reverse a Linked list using,
1. Recursive Algorithm.
2. Iterative Algorithm.

 Lets understand what is the input and the expected output.

Algorithm (Recursive Algorithm)

---

Note: we have to work on the linked list in reversed way, that is we need access to last node of the list and then second last node and so on as we need to reverse their pointers.

STEP 1: Recursively break the nodes of the linked list one by one so that we can access them in reversed way.                
STEP 2: When we encounter the last node, return, now we have access to last and second last node, this is the step where we also have access to head of our reversed list, so we need to preserve that and keep returning it in each call to pass it to caller.
STEP 3: Once we have access to the last and second last node, reverse there pointers but by taking the help of only current node. continue till the first node of the list and return.

Reverse linked list recursively java program.

---

package com.javabypatel.program;

public class ReverseLinkedListUsingRecursion {
    Node startNode;

    public static void main(String[] args) {
        ReverseLinkedListUsingRecursion reverseTheLinkedList = new ReverseLinkedListUsingRecursion();
        reverseTheLinkedList.addNode(new Node(10));
        reverseTheLinkedList.addNode(new Node(20));
        reverseTheLinkedList.addNode(new Node(30));
        reverseTheLinkedList.addNode(new Node(40));
        reverseTheLinkedList.addNode(new Node(50));

        //Print List
        System.out.println("Original List is: ");
        reverseTheLinkedList.printLinkList(reverseTheLinkedList.startNode);

        Node reverseListHead = reverseTheLinkedList.reverseLinkListRecursively(reverseTheLinkedList.startNode);

        //Reverse List
        System.out.println("\nReverse List is: ");
        reverseTheLinkedList.printLinkList(reverseListHead);
    }

    public Node reverseLinkListRecursively(Node node){

        if (node == null || node.getNext() == null) {
            return node;
        }

        //Note: we have to preserve reversedNodesStartPointer as that will be start node of Reversed link list
        Node reversedNodesStartPointer = reverseLinkListRecursively(node.getNext());

        //Ideally we want to do like code below, but we will lose startPointer of reversed list as we are modifying reversedNodesStartPointer
        //So to keep our reversedNodesStartPointer intact we will achieve the same thing but without disturbing reversedNodesStartPointer.
        //reversedNodesStartPointer.setNext(node);
        //node.setNext(null);
        //return node;

        // equivalent to step reversedNodesStartPointer.setNext(node);
        // node.getNext() points to same node referenced by reversedNodesStartPointer
        node.getNext().setNext(node);
        node.setNext(null);

        //Keep returning head of reversed nodes in each call till end, so can be passed to caller.
        return reversedNodesStartPointer;
    }

    private void printLinkList(Node startNode) {
        Node tempNode = startNode;
        while(tempNode!=null){
            System.out.print(tempNode.getData() + " ");
            tempNode = tempNode.getNext();
        }
    }

    private void addNode(Node node) {
        if (startNode != null) {
            Node tempNode = startNode;
            while (tempNode.getNext() != null) {
                tempNode = tempNode.getNext();
            }
            tempNode.setNext(node);
        } else {
            this.startNode = node;
        }
    }
}

public class Node{
 
 private int data;
 private Node next;
 
 public Node(int data) {
  this.data = data;
 }
 public int getData() {
  return data;
 }
 public void setData(int data) {
  this.data = data;
 }
 public Node getNext() {
  return next;
 }
 public void setNext(Node next) {
  this.next = next;
 }
}

You may also like to see

---

Reverse Linked list Iteratively

Detect loop in linked list

Reverse Linked list in Java

Find Nth node from last in a linked list

Sort Linked list.

Clone Linked list.

How is ambiguous overloaded method call resolved in java

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.