Logo
×

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:

How to reverse a linked list in java

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:

How to reverse a linked list in java

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:

How to reverse a linked list in java

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:

How to reverse a linked list in java

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.

Related Topics

Stack Program in Java

Stack Program in Java The Stack class is part of the collection framework that inherits the Vector class. Thus, the Stack class can also be called a subclass of the Vector...

5 minutes read.

Java Double Keyword

In java primitive data types, we have two different types of data types which are Boolean and floating-point data types.In floating data type again we have four types which are...

3 minutes read.

SHA Decrypt in Java

In this section, we will be acknowledged about the decryption of SHA in Java. Java SHA The SHA cryptographic hash algorithm in cryptography outputs the hash value as an approximately 40-digit-long hexadecimal...

4 minutes read.

Catalan number in Java

In general mathematics, Catalan numbers can be defined as the sequence of natural numbers that frequently occur in counting problems often encountered in recursively defined objects. Mathematical formula of Catalan number Coming...

3 minutes read.

Java Snippets

The term "snippet" refers to a section of code that addresses numerous issues with just a few lines of code. Decreases the number of lines of code and improves programmer...

3 minutes read.

Java Program to Sort an Array of 0's, 1's, and 2’s | Dutch National Flag Problem in Java

The famed Dutch computer programmer Edsger Dijkstra's Dutch Nation Flag (DNF) challenge ranks among the most well-known programming challenges. The Dutch tricolor flag, comprising red, white, and blue, is the...

3 minutes read.

Java String concat() method:

Java String concat() method is used to add the given String to the end of the current String. Syntax: public String concat(String str) Parameter: Str: String to be concatenated at the end of current...

1 minute read.

Java String format() method

format() method returns a formatted String based on the given locale,specified format and arguments. Syntax: public static String format(String format , Object… args) Parameter: locale : It specifies locale value to be applied on...

2 minutes read.

Equidigital in Java

In this section, we will understand what is an equidigital number and how to write Java programs to locate them. It is commonly asked in academic settings and Java coding...

4 minutes read.

Type Annotations in Java

Only declarations were eligible for annotations in earlier versions of Java. With Java 8, you may now annotate any type use, including types in declarations, generics, and casts: @Encrypted String data; List<@NonNull...

6 minutes read.

Java Math scalb() Method

The scalb() method of Java Math class returns a single perfectly rounded product of floating-point and member of the double value set as if performed by d*2scaleFacor rounded value. Syntax: public static...

2 minutes read.

Maximizing Profit in Stock Buy Sell in Java

In this tutorial, we will deal with a popular problem, a favourite of interviewers. The problem is named as Maximising profit in stock Buy Sell. we will see certain approaches...

6 minutes read.

Set Up the Environment in Java

The Java is regarded as the pure object-oriented programming language. The Java applications are first compiled into the byte-code and then run by using the JVM. The Java is the...

4 minutes read.

How to Convert String to Object in Java

How to Convert String to Object in Java The Object is the super class of all classes. So you can assign a string to Object directly. There are two methods to...

3 minutes read.

Methods in Java

The Methods in Java are the collection of statements that are executed when the method is called. By using the methods, the complexity of writing the code decreases. The method consists...

4 minutes read.

Default Virtual Behaviour in C++ vs Java

Virtual Behaviour in C++: The class member methods in C++ are, by default, non-virtual. This implies that by simply defining it, they can be turned into virtual. The virtual class can be...

3 minutes read.

Java Math cos() Method

The cos() method of Math class returns the trigonometric cosine of the specified angle. Syntax: public static double cos(double a) Parameters: The parameter ‘a’ represents an angle measured in radians. Return Value: The cos() method returns...

1 minute read.

Java String vs StringBuffer

Java String vs StringBuffer In this section, we will discuss the key differences between String and StringBuffer class. Before moving to the ahead in this section, let’s introduce with both classes. String...

4 minutes read.

Java concurrency interview questions

During technical interviews, one of the most challenging and sophisticated subjects is concurrency in Java. This page offers responses to some of the related interview questions you might come across. 1....

11 minutes read.

Java BufferedWriter

BufferWriter Class: It is used to write the data more efficiently. This class is present in the java.io package, it inherits the data from the Writer class. Writer class is...

4 minutes read.