Linked List: Program to reverse a linked list using recursive approach

Write a program to reverse a linked list using recursive method

Linked list is a series of nodes in which each node contains a data field and
reference (pointer) to the next node in the list. Using the reference pointer(next) between nodes, it forms a chain of nodes connected to each other.

Example

Imagine the following linked list that has 5 nodes:
20 -> 30 -> 60 -> 50 -> 10

Recursive Approach

In this approach we pass two parameters to the recursive function

1. Two nodes act as parameters: one is next and other is previous
2. If next is not NULL perform the following
   • reverseRecursive(next.next, next);
   • next.next = previous;
3. Else set head node of linked list on previous

Complexity

Time Complexity : O(n) , where n is the size of linked list
Space Complexity : O(1)

Java Code

import java.util.*;

class ReverseLinkedListRecursive {
 
    class Node {
        // initialising data field and next pointer of node
        int data;
        Node next;
     
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
     
    Node head;
 
    // insertion of node in linked list
    public void insert(int new_data) {
        Node temp = new Node(new_data);
        temp.next = head;
        head = temp;
    }
    //function for printing linked list
    public void printLinkedlist() {
        List allNodesList = new ArrayList<>();
        Node temp = head;
        while (temp != null) {
            allNodesList.add(Integer.toString(temp.data));
            temp = temp.next;
        }
        System.out.println(String.join(" -> ", allNodesList));
    }
 
    // recursive function for reversing linkedlist
    public void reverseRecursive(Node next, Node previous)            
    {
        if(next != null)
        {
            reverseRecursive(next.next, next);
            next.next = previous;
        }
        else{
            head = previous;
        }
    }
 
    public static void main(String[] args) {
        // initialising object of linkedlist class
        ReverseLinkedListRecursive ll = new ReverseLinkedListRecursive();
        ll.insert(10);
        ll.insert(50);
        ll.insert(60);
        ll.insert(30);
        ll.insert(20);
 
        // call for recursive function
        System.out.println("Using Recursive Approach ");
        System.out.println("Original Linked List ");
        ll.printLinkedlist();
        System.out.println("Reversed Linked List ");
        ll.reverseRecursive(ll.head, null);
        ll.printLinkedlist();
 
    }
    
  
}

Output

Using Recursive Approach
Original Linked List
20 -> 30 -> 60 -> 50 -> 10
Reversed Linked List
10 -> 50 -> 60 -> 30 -> 20