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

Java FileOutputStream

What is FileOutputStream?When we need raw stream data written into a file, we need to look for another option: FileOutputStream. It is used when the file's data is byte-oriented. It comes under...

4 minutes read.

Difference between String, StringBuffer and StringBuilder in java

What is a string in Java? Strings are a collection of characters that are commonly used in Java programming. Strings are regarded as objects in the Java programming language. “String” is a...

4 minutes read.

How to Round Double Float up to Two Decimal Places in Java

It indicates 15 digits just after the decimal place in Java whenever a double data type is used in front of a variable. For example, when representing rupees and other...

4 minutes read.

Stack in Java

Java provides a number of collection frameworks to store the collection of objects. Among the collection of data structures " Stack " is one of them. Stack is one of...

5 minutes read.

Java Transient Keyword

An object in Java can be turned into a stream of bytes using serialization. The data of the instance and the kind of data saved in that instance are both...

3 minutes read.

Rehashing in Java

The most crucial idea mostly in the data structure is hashing, which is utilized to change a particular key into some other value. The hash function can be used to...

7 minutes read.

Java Return Keyword

The return keyword in Java is used to end a method's execution. the caller receives the return, followed by the appropriate value. The return type of the method, such as...

3 minutes read.

Pig Latin Program in Java

Pig Latin Program in Java Pig Latin is a method for translating words of the English language into a different language. It is an encrypted word that is generated by using the following steps....

4 minutes read.

How to Convert Octal to Decimal in Java

How to Convert Octal to Decimal in Java There are two methods to convert Octal to Decimal: Using parseInt() method Using user-defined logic Using Integer.parseInt() method The Integer.parseInt() method is a static method...

2 minutes read.

Java exception list

Java uses exceptions, like the majority of contemporary programming languages, to deal with both errors and "extraordinary events." When an exception arises inside the program, it messes up the regular...

6 minutes read.

How to Run Applet Program in Java

An applet is a new type of program which is put in a webpage. By inserting applet into a webpage dynamic content can be created. Characteristics of an Applet The applet is...

11 minutes read.

Object Definition in Java

In this article, you will be acknowledged about object in Java, its definition and how is this useful in writing the programs in Java. The comprehension of object-oriented technology depends on...

4 minutes read.

Ganesha’s Pattern in Java

This part teaches us how to use stars and other special characters to write Ganesha's Pattern in Java programming. Among the most challenging Java pattern applications to code. The Ganesha will be...

3 minutes read.

Static() Function in Java

The static keyword in Java is suitable for variables, constants, and functions. The static keyword is mainly used to control storage so that it may be appropriately used. We shall...

3 minutes read.

MessageDigest in Java

The compression of mathematical numbers is accomplished using hash functions. In almost every data security application, hash functions are employed. The hashing, often called has values, returns a value called...

3 minutes read.

How to Convert double to int in Java

The double is a larger data type than int. When we assign a larger type value to a variable of smaller type, then we need to perform the explicit conversion....

2 minutes read.

Differences between Set and List in Java

Set in Java: The Java. util package contains an interface called the set. The set interface expands the Collection interface. A collection interface is an unordered collection of List where duplicates...

6 minutes read.

Flag Pattern in Java

The flag pattern in Java can be printed, which will be covered in this part. Given how difficult they are to code, flag patterns are rarely asked by interviewers. We separate...

2 minutes read.

Difference between next() and nextline() in Java

One of the simplest methods for receiving input of the basic data types, also including int, double, and strings, in Java, is to use the Scanner class, which is part...

3 minutes read.

For Loop Program in Java

For Loop Program in Java The for-loop program in Java is written when we want a particular set of statements to be executed repeatedly until the given criteria/ condition is met....

8 minutes read.