How to reverse a linked list in java

The process of reversing a linked list in Java will be covered in this section. One of the most common questions in interviews is about reversing a linked list. If the linked list's head or initial node is known, the goal is to reverse the list.

Given: The head of the linked list or its first node (which is 2 in our case)

2 - > 6 - > 3 - > 4 - > 9 - > 1 - > 8 -> 5 - > 7 - > Null

Return:

7 - > 5 - > 8 - > 1 - > 9 - > 4 - > 3 - > 6 - > 2 - > Null

Given:

7 - > 5 - > Null

Return:

5 - > 7 - > Null

Given:

4 - > Null

Return:

4 - > Null

Given:

Null

Return:

Null

There are two methods for resolving the issue. These two strategies are:

• Recursive Approach
• Iterative Approach

Let's start by talking about the Recursive strategy.

Reversing a LinkedList using a Recursive Approach

The recursive technique includes the steps listed below.

Step 1: separate the list into its first node and the remaining linked list nodes.

Step 2: Call the reverseList() method on the linked list's remaining elements.

Step 3: Connect the remainder to the first.

Step 4: Adjust the head pointer.

Implementation

The execution of the linked list reversal using the aforementioned steps is demonstrated in the following code.

// RecursiveApproach.java

public class RecursiveApproach  
{  
// the list's head node or first node 
static LinkedListNode head;   
static class LinkedListNode   
{  
// for storing the value of a node  
int v;  
// the following pointer refers to the following list node or to null  
LinkedListNode next;  
// constructor for the class  
LinkedListNode(int e)  
{  
// putting the values in  
v = e;  
next = null;  
}  
}  
  
// a technique that reverses the list  
public LinkedListNode reverseList(LinkedListNode head)  
{  
// if the list or the head is empty
// includes only one entry then inverting the list
// does not affect the list in any way. Consequently, we
// without making any operations can return the initial list.
if (head == null || head.next == null)  
{  
return head;  
}  
// reverse the remaining items on the list and put
// the last item on the list is the first one   
LinkedListNode r1 = reverseList(head.next);  
head.next.next = head;  
head.next = null;  
// correcting the head pointer  
return r1;  
}  
 /* Displaying the connected list in this way */  
public void printList(LinkedListNode h1)  
{  
LinkedListNode t1 = h1;  
while (t1 != null)   
{  
System.out.print(t1.v + " ");  
// going to the following node  
t1 = t1.next;  
}  
System.out.println();  
}  
// main method  
public static void main(String args[])  
{  
// creating an instance to the class RecursiveApproach  
RecursiveApproach lo = new RecursiveApproach();  
// 2 -> NULL  
lo.head = new LinkedListNode(2);  
// 2 -> 6 -> NULL  
lo.head.next = new LinkedListNode(6);  
// 2 -> 6 -> 3 -> NULL  
lo.head.next.next = new LinkedListNode(3);  
// 2 -> 6 -> 3 -> 4 -> NULL  
lo.head.next.next.next = new LinkedListNode(4);  
// 2 -> 6 -> 3 -> 4 -> 9 -> NULL  
lo.head.next.next.next.next = new LinkedListNode(9);  
 // 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> NULL  
lo.head.next.next.next.next.next = new LinkedListNode(1);  
// 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> NULL  
lo.head.next.next.next.next.next.next = new LinkedListNode(8);  
// 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> 5 -> NULL  
lo.head.next.next.next.next.next.next.next = new LinkedListNode(5);
 // 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> 5 -> 7 -> NULL
lo.head.next.next.next.next.next.next.next.next = new LinkedListNode(7);  
 System.out.println(" Before reversal, the linked list is: ");  
lo.printList(head);  
head = lo.reverseList(head);  
System.out.println(" ");  
System.out.println(" The linked list is reversed after reversal: ");  
lo.printList(head);  
}  
}  

Output:

Space and Time Complexity:

The program described above has an O(n) time complexity and an O(1) space complexity, where n is the total number of nodes in the list. Because of the recursion, the program above uses the built-in stack. We have omitted the area taken up by the built-in stack for the sake of simplicity.

Reversing a LinkedList using an Iterative Approach

The iterative technique includes the phases listed below.

Step 1: Initialise the 3 (previous, current, and next) as follows.

current = head, previous = NULL, and next = NULL.

Step 2: Using a loop to go through the linked list, do the following.

// Retain the next node before 
// modifying the currents next.
next = current -> next
// The reversing is now accomplished by 
// switching the direction of the current.
Current -> next = previous
// advancing the past and present by one step
Previous = current
Current = next

Implementation

The execution of a linked list reversal using the aforementioned steps is demonstrated in the following code.

// IterativeApproach.java

public class IterativeApproach   
{  
// the list's head node or first node 
static LinkedListNode head;  
// a class for building linked list nodes
// The value of a node in a linked list and 
// a pointer to another node are the two things 
// that a node in the list fetches.
static class LinkedListNode   
{  
int v;   
LinkedListNode next;  
// constructor for the class   
LinkedListNode(int no1)  
{  
v = no1;  
next = null;  
}  
}  
// a technique that reverses the list   
LinkedListNode reverse(LinkedListNode node)  
{  
//initializing in accordance 
// with the specified stages  
LinkedListNode previous = null;  
LinkedListNode current = node;  
LinkedListNode next = null;  
while (current != null)   
{  
next = current.next;  
current.next = previous;  
previous = current;  
current = next;  
}  
node = previous;  
return node;  
}  
// reveals the connected list's content  
void printList(LinkedListNode nd)  
{  
while (nd != null)   
{  
System.out.print(nd.v + " ");  
nd = nd.next;  
}  
}  
// main method  
public static void main(String args[])  
{  
// creating an instance to the class IterativeApproach   
IterativeApproach lo = new IterativeApproach();  
// 2 -> NULL  
lo.head = new LinkedListNode(2);  
// 2 -> 6 -> NULL  
lo.head.next = new LinkedListNode(6);  
// 2 -> 6 -> 3 -> NULL  
lo.head.next.next = new LinkedListNode(3);  
// 2 -> 6 -> 3 -> 4 -> NULL  
lo.head.next.next.next = new LinkedListNode(4);  
// 2 -> 6 -> 3 -> 4 -> 9 -> NULL  
lo.head.next.next.next.next = new LinkedListNode(9);  
 // 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> NULL  
lo.head.next.next.next.next.next = new LinkedListNode(1);  
// 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> NULL  
lo.head.next.next.next.next.next.next = new LinkedListNode(8);  
// 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> 5 -> NULL  
lo.head.next.next.next.next.next.next.next = new LinkedListNode(5);
 // 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> 5 -> 7 -> NULL
lo.head.next.next.next.next.next.next.next.next = new LinkedListNode(7);  
System.out.println(" Before reversal, the linked list is: "); 
lo.printList(head);  
head = lo.reverse(head);  
System.out.println("\n");  
System.out.println(" The linked list is reversed after reversal: ");  
lo.printList(head);  
}  }  

Output:

Space and Time complexity:

The given program has a time complexity of O(n), yet its spatial complexity is O(1), where n is the number of nodes in the list.

Reversing a LinkedList using Stack

The preceding are the processes that are taken while utilizing a stack to reverse a linked list.

Step 1: Continue to enter node values into the stack after each one has been entered.

Step 2: Modify the Head pointer in step 2 with the content of the list's final node.

Step 3: Once the stack is empty, begin adding the contents of the nodes to the head node and continue doing so.

Step 4: Check to see that the list's last node points to NULL when the appending process is complete.

Implementation

Only with help of the previously mentioned steps, the linked list is reversed in the following code.

// StackApproach.java

// significant import assertion 
import java.util.*;  
public class StackApproach  
{  
// the list's head node or first node 
static LinkedListNode head;   
static class LinkedListNode   
{  
// for holding the node's value
int v;  
// the next pointer either link to the second node 
// on the list or to null.
LinkedListNode next;  
// constructor for the class  
LinkedListNode(int d1)  
{  
// putting the values in 
v = d1;  
next = null;  
}  
}  
// a technique that reverses the list   
public LinkedListNode reverseList(LinkedListNode head, Stack<Integer> stck)  
{  
//Reversing the list does not affect it if the 
// head is empty or there is only one element 
// in the list. As a result, we may just provide 
// the original list without making any changes. 
if (head == null || head.next == null)  
{  
return head;  
}  
// iterating through the list and 
// adding the nodes' values to the stck  
while(head != null)  
{  
    stck.push(head.v);  
    head = head.next;  
}  
// The initial node of the inverted 
// linked list is referred to as h1.  
LinkedListNode h1 = null;  
while(stck.empty() == false)   
{  
if(head == null)  
{  
// making the inverted linked lists 
// initial node
h1 = new LinkedListNode(stck.peek());  
head = h1;  
stck.pop();  
}  
else  
{  
// all remaining nodes of a reversed 
// linked list is created  
head.next = new LinkedListNode(stck.peek());  
stck.pop();  
head = head.next;  
}  
}  
// the very first node of a 
// reversed linked list will be returned.
return h1;  
}  
/* Displaying the connected list in this way  */  
public void printList(LinkedListNode h2)  
{  
LinkedListNode t1 = h2;  
while (t1 != null)   
{  
System.out.print(t1.v + " ");  
// going to the following node  
t1 = t1.next;  
}  
System.out.println();  
}  
// main method  
public static void main(String args[])  
{  
// creating an instance for the class StackApproach
StackApproach lo = new StackApproach();  
// 2 -> NULL  
lo.head = new LinkedListNode(2);  
// 2 -> 6 -> NULL  
lo.head.next = new LinkedListNode(6);  
// 2 -> 6 -> 3 -> NULL  
lo.head.next.next = new LinkedListNode(3);  
// 2 -> 6 -> 3 -> 4 -> NULL  
lo.head.next.next.next = new LinkedListNode(4);  
// 2 -> 6 -> 3 -> 4 -> 9 -> NULL  
lo.head.next.next.next.next = new LinkedListNode(9);  
 // 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> NULL  
lo.head.next.next.next.next.next = new LinkedListNode(1);  
// 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> NULL  
lo.head.next.next.next.next.next.next = new LinkedListNode(8);  
// 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> 5 -> NULL  
lo.head.next.next.next.next.next.next.next = new LinkedListNode(5);
 // 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> 5 -> 7 -> NULL
lo.head.next.next.next.next.next.next.next.next = new LinkedListNode(7);  
// creating an instance for the class Stack  
// the new stack will be void.  
Stack<Integer> stck = new Stack<Integer>();  
System.out.println(" Before reversal, the linked list is:  ");  
lo.printList(head);  
head = lo.reverseList(head, stck);  
System.out.println(" ");  
System.out.println(" The linked list is reversed after reversal:  ");  
lo.printList(head);  
}  
}

Output:

Space and Time Complexities:

The preceding program has a time complexity of O(n), and it also has a space complexity of O(n), where n is the total amount of nodes in the list.

Reversing a LinkedList using an Array

The processes involved in utilizing an array to reverse a linked list are as follows.

Step 1: First, determine how many nodes are in the provided list.

Step 2: Prepare an integer array in Step 2 such that its size is comparable to the length of the list.

Step 3:  Fill the array with the values of the nodes in the list from left to right by iterating through the list.

Step 4: A list is formed by taking each element of the array one at a time, starting at the end of the array, with the final element serving as the list's head. The second node of the list is formed from the second-to-last element of the array, and so on.

Implementation

With the help of the previously mentioned steps, the linked list is reversed in the following code.

// ArrayApproach.java

// significant import assertion   
import java.util.*;  
public class ArrayApproach  
{  
// the list's head node or first node  
static LinkedListNode head;   
static class LinkedListNode   
{  
// for holding the node's value 
int v;  
// the next pointer either link to the second node 
LinkedListNode next;  
// constructor for the class  
LinkedListNode(int d1)  
{  
// putting the values in   
v = d1;  
next = null;  
}  
}  
// a method for counting all of the 
// nodes in the linked list 
public int countNodes(LinkedListNode head)  
{  
// The linked list's total number of
// nodes are stored in variable c.  
int c = 0;  
while(head != null)  
{  
// adding one to the total
c = c + 1;  
// advancing the head one more step  
head = head.next;  
}  
return c;  
}  
// a technique that reverses the list    
public LinkedListNode reverseList(LinkedListNode head, int s)  
{  
// array to store the linked list's nodes' values 
int a[] = new int[s];  
// populating the array with loops  
for(int k = 0; k < s; k++)  
{  
a[k] = head.v;  
head = head.next;  
}  
// j holds the array's last index, a. 
int j = s - 1;  
// The initial node of the inverted 
// linked list is referred to as h1.  
LinkedListNode h1 = null;  
while(j >= 0)  
{  
      
if(h1 == null)  
{  
// making the inverted linked lists 
// initial node
h1 = new LinkedListNode(a[j]);  
head = h1;  
}  
else  
{  
// generating and adding the remaining nodes 
// to the h1 of a reversed linked list 
head.next = new LinkedListNode(a[j]);  
head = head.next;  
}  
// iterating from end to beginning   
// therefore, decreasing the j by 1  
j = j - 1;  
  
}  
// the very first node of a 
// reversed linked list will be returned.
return h1;  
}  
/* Displaying the connected list in this way  */  
public void printList(LinkedListNode h2)  
{  
LinkedListNode t1 = h2;  
while (t1 != null)   
{  
System.out.print(t1.v + " ");  
// going to the following node  
t1 = t1.next;  
}  
System.out.println();  
}  
// main method  
public static void main(String args[])  
{  
// creating an instance for the class ArrayApproach  
ArrayApproach lo = new ArrayApproach();  
// 2 -> NULL  
lo.head = new LinkedListNode(2);  
// 2 -> 6 -> NULL  
lo.head.next = new LinkedListNode(6);  
// 2 -> 6 -> 3 -> NULL  
lo.head.next.next = new LinkedListNode(3);  
// 2 -> 6 -> 3 -> 4 -> NULL  
lo.head.next.next.next = new LinkedListNode(4);  
// 2 -> 6 -> 3 -> 4 -> 9 -> NULL  
lo.head.next.next.next.next = new LinkedListNode(9);  
 // 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> NULL  
lo.head.next.next.next.next.next = new LinkedListNode(1);  
// 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> NULL  
lo.head.next.next.next.next.next.next = new LinkedListNode(8);  
// 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> 5 -> NULL  
lo.head.next.next.next.next.next.next.next = new LinkedListNode(5);
 // 2 -> 6 -> 3 -> 4 -> 9 -> 1 -> 8 -> 5 -> 7 -> NULL
lo.head.next.next.next.next.next.next.next.next = new LinkedListNode(7);  
System.out.println(" Before reversal, the linked list is: "); 
lo.printList(head);  
// the total amount of nodes with 
// in the linked list is known as size. 
int s = lo.countNodes(head);  
head = lo.reverseList(head, s);  
System.out.println(" ");  
System.out.println(" The linked list is reversed after reversal: ");  
lo.printList(head);  
}  
}  

Output:

Space and Time complexity:

The preceding program has a time complexity of O(n), and it also has a space complexity of O(n), where n is the total number of nodes in the list.