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.