Reverse a Linked List - Recursive

Given a linked list having n nodes. Reverse the list using recursive approach.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Preparing for interviews? IDeserve team is here to help.




Algorithm/Insights

Start with node curr as head.
1. If curr is null, return.
2. If curr's next element is null, this means it is the last node, so make this as head because the last node will be the head of reversed list. Return.
3. Recursively traverse the list.
4. Set curr->next->next to curr.
5. Set curr->next to null


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




Code Snippet

			
package com.ideserve.saurabh.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * <br><br>
 * Reverse a linked list - Recursive Solution</b><br>
 * Given a linked list having n nodes. Reverse the list by nodes using recursive strategy.
 * <br><br>
 * Example: <br>
 * Linked List: <br>
 * 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> X
 * <br>
 * Output: <br>
 * 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> X
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=MRe3UsRadKw">Reverse a linked list - Recursive Solution Youtube Link</a> 
 * @author Saurabh
 *
 */
public class ReverseLinkedListRecursive {
	
	private Node head;

	public Node getHead() {
		return head;
	}

	public void setHead(Node head) {
		this.head = head;
	}
	
	public void reverseLinkedListRecursive() {
		reverseLinkedListRecursive(head);
	}
	
	private void reverseLinkedListRecursive(Node curr) {

        if (curr == null) {
            return;
        }

        if (curr.getNext() == null) {
            this.head = curr;
            return;
        }

        reverseLinkedListRecursive(curr.getNext());
        curr.getNext().setNext(curr);
        curr.setNext(null);
    }
	
	/* 
	 * ******************************************************
	 * Following methods are for testing the solution
	 * ******************************************************
	 */
    public static void main(String[] args) {
		
    	ReverseLinkedListRecursive list = new ReverseLinkedListRecursive();
		list.createTestList(5);
		list.printlist();
		list.reverseLinkedListRecursive();
		list.printlist();
	}

	/*
	 * Create a test list having n nodes from 1 to n 
	 */
	public void createTestList(int n) {
		
		if(n < 1)
			return;
		
		int i = 1;
		Node temp = null;
		while(i <= n) {
			Node node = new Node(i);		
			if(head == null) {
				head = node;
				temp = head;
			} else {
				temp.setNext(node);
				temp = node;
			}
			i++;
		}
	}
	
	/*
	 * Print the list
	 */
	public void printlist() {
		
		Node temp = head;
		while(temp != null) {
			System.out.print(temp.getData() + " -> ");
			temp = temp.getNext();
		}
		System.out.println("X");
	}
	
	/**
	 * Defines a linked list node class
	 * @author Saurabh
	 *
	 */
	class Node {

		private int data;
		private Node next;

		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;
		}

		public Node(int data) {
			super();
			this.data = data;
		}

	}
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.

    Saurabh Kumar

    Ninja Programmer