Dinesh on Java

In this article, we will discuss how to reverse linked list in java. Iterative and Recursive there are two approaches, we can use to find the solution to this problem. As we know that, a linked list has several nodes, and each node in the list has the content and a pointer to the next node in the list. It does not store any pointer to the previous node. To store a single linked list, only the pointer to the first node in that list must be stored. The last node in a single linked list points to nothing.
In the previous articles, we have discussed several algorithms related to the liked list like the following:

• Find the nth element in a linked list
• A middle element in a linked list

Reverse linked list

Input
A linked list, the task is to reverse the linked list.

Output
Reverse the linked list and return the head of the modified list.

For Example:

Input : ->1->2->3->4->5->6->7->8->9

Reversed : ->9->8->7->6->5->4->3->2->1

Let’s discuss the following two approaches to reverse a linked list.

Approach 1: Iterative

In this approach, we will use iterative strategy to reverse linked list with the following steps:
Step 1: We create 3 nodes such as currentNode, previousNode and nextNode.
Step 2: Let’s initialize them as currentNode = head, previousNode = null and nextNode = null.
Step 3: Now move these nodes and keep reversing these pointers one by one till currentNode != null.
Step 4: Finally, set head = previousNode.

Let’s see the code:

private static Node reverseUsingIteration(Node head)	{
        if(head.getNext() == null) {
        	return head;
        }
        Node currentNode = head;
        Node nextNode = null;
        Node previousNode = null;
        		
        while(currentNode != null) {
        	nextNode = currentNode.getNext();
        	currentNode.setNext(previousNode);
        	previousNode = currentNode;
            currentNode = nextNode;
        }
        return previousNode;
	}

Let’s discuss another approach to reverse linked list using recursion.

Approach 2: Recursive

In this approach, we will use recursive strategy to reverse linked list with the following steps:

Step 1: Let’s consider a node head and pass to the reverseUsingRecursion(head) method
Step 2: If head.next is null return head.
Step 3: Now head.next is not null the call reverseUsingRecursion(head.next)
Step 4: And set head.next = head and head.next=null

Let’s see the code like the following:

private static Node reverseUsingRecursion(Node head)	{
        if(head.getNext() == null) {
        	return head;
        }
        Node newHead = reverseUsingRecursion(head.getNext());
        head.getNext().setNext(head);
        head.setNext(null);
        return newHead;
	}

Let’s see the complete code:

/**
 * 
 */
package com.dineshonjava.algo;

import java.util.Optional;

/**
 * @author Dinesh.Rajput
 *
 */
public class LinkedListTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Node listNode = createLinkedList(9);
		System.out.println("Print List Before Reverse");
		printList(listNode);
		listNode = reverseUsingRecursion(listNode);
		System.out.println("Print List After Reverse using Recusion");
		printList(listNode);
		
		System.out.println("Print List Before Reverse");
		printList(listNode);
		listNode = reverseUsingIteration(listNode);
		System.out.println("Print List After Reverse using Iteration");
		printList(listNode);
	}
	
	private static Node createLinkedList(int n) {
	    Node head = new Node("1");
	    Node current = head;
	 
	    for (int i = 2; i <= n; i++) {
	        Node newNode = new Node(String.valueOf(i));
	        current.setNext(newNode);
	        current = newNode;
	    }
	 
	    return head;
	}
	
	private static Node reverseUsingIteration(Node head)	{
        if(head.getNext() == null) {
        	return head;
        }
        Node currentNode = head;
        Node nextNode = null;
        Node previousNode = null;
        		
        while(currentNode != null) {
        	nextNode = currentNode.getNext();
        	currentNode.setNext(previousNode);
        	previousNode = currentNode;
            currentNode = nextNode;
        }
        return previousNode;
	}
	
	private static Node reverseUsingRecursion(Node head)	{
        if(head.getNext() == null) {
        	return head;
        }
        Node newHead = reverseUsingRecursion(head.getNext());
        head.getNext().setNext(head);
        head.setNext(null);
        return newHead;
	}
	
	public static void printList(Node head) {
		while (head != null) {
			System.out.print(head.getData());
			head = head.getNext();
	    }
		System.out.println();
	}
}

Run above program, you will get the following output:

Print List Before Reverse
->1->2->3->4->5->6->7->8->9

Print List After Reverse using Recusion
->9->8->7->6->5->4->3->2->1

Print List Before Reverse
->9->8->7->6->5->4->3->2->1

Print List After Reverse using Iteration
->1->2->3->4->5->6->7->8->9

Hope, you have understood this solution for the above to reverse a linked list. Please share other solutions if you have. :).

Happy learning with us!!!.