Reverse Linked List in Java

A data structure consisting of nodes where data and a pointer is present in every node and the pointer points to the next node is called a Linked list which is different from an array, and when such a linked list is reversed, it is called reversed linked list. In which the list is divided into two parts called the first node of the list and the rest of the linked list, among which reverse function is called for the rest of the linked list and the rest of the linked list is linked to the first node, and the head pointer is fixed. In this topic, we are going to learn about Reverse Linked List in Java.

Start Your Free Software Development Course

Web development, programming languages, Software testing & others

Working of reverse linked list in Java

A linked list can be reversed in java using two algorithms. They are:

1. Iterative Algorithm

The steps below describe how an iterative algorithm works:

• Three-pointers must be initialized, which are called ptrA, ptrB and ptrC.
• The ptrA is pointing in the first place. This is the task of ptrA. ptrB uses ptrA as a reference to point back. Since the last node in the reversed list is null, initially, this pointer will also be null.
• The ptrB is pointing to the second place. This is the main pointer. The next of ptrB’s is pointed to ptrA, and this is how the existing link of pointers is reversed.
• The third place is being pointed by the ptrC. Using this pointer is for backup to make sure the list is not lost ahead of ptrB; otherwise, it causes loss of references ahead of ptrB.
• The reversing of the linked list begins by initializing the ptrA to Null. It must be set to null because ptrA will be the tail node after reverse the linked list.
• The next of ptrB is linked to ptrA because the ptrB, which is pointing to the first node, becomes the tail node in the reversed list.
• If the list consisting of just one node needs to be reversed, then following the above two steps can complete the task.
• The reference to the list ahead of ptrB will be lost when ptrB’s next is made to point to ptrA. So we will use ptrC as a backup to the ahead list of ptrB before pointing ptrB’s next to ptrA.
• The above steps are repeated until the ptrB is pointing to null, which means that all the original list nodes are reversed.

2. Recursive Algorithm

The steps below describe how a recursive algorithm works:

• The algorithm begins by considering the node current as of the head.
• If the node current is null, then it is returned.
• If the next element of the current node is null, it indicates it is the last node in the list. The head of the reversed list must be the last node, and hence the last node must be made as head and then return.
• The list is traversed recursively.
• The current is set to current.next.next.
• Null is set to current.next.

Examples of Reverse Linked List in Java

Here are the following examples mention below

Example #1

Java program to reverse a singly linked list using an iterative algorithm

Code:

class List
{
static Node head1;
static class Node
{
int data1;
Node nex;
Node(int d1)
{
data1 = d1;
nex = null;
}
}
//The linked list is reversed using this function
Node reverselist(Node node1)
{
Node previous = null;
Node curr = node1;
Node nex = null;
while (curr != null)
{
nex = curr.nex;
curr.nex = previous;
previous = curr;
curr = nex;
}
node1 = previous;
return node1;
}
// The contents of linked list are printed
void printL(Node node1)
{
while (node1 != null)
{
System.out.print(node1.data1 + " ");
node1 = node1.nex;
}
}
public static void main(String[] args)
{
//The values to be inserted in the list before reversing are given here
List l = new List();
l.head1 = new Node(30);
l.head1.nex = new Node(40);
l.head1.nex.nex = new Node(50);
l.head1.nex.nex.nex = new Node(60);
System.out.println("The items in the linked list that needs to be reversed are");
l.printL(head1);
//Function to reverse the list is called here
head1 = l.reverselist(head1);
System.out.println("");
System.out.println("The items in the reversed linked list are");
l.printL(head1);
}
}

Output:

Example #2

Java program to reverse a singly linked list using an iterative algorithm

Code:

class List {
static Node head1;
static class Node {
int data1;
Node nex;
Node(int d1)
{
data1 = d1;
nex = null;
}
}
// A recursive function to reverse the linked list
Node reverse(Node current, Node previous)
{
//Last node is marked as head
if (current.nex == null) {
head1 = current;
//previous node is updated with next
current.nex = previous;
return head1;
}
//current.nex node is saved for the recursive call
Node nex1 = current.nex;
//nex is updated
current.nex = previous;
reverse(nex1, current);
return head1;
}
// Content of the reversed linked list are printed
void printL(Node node)
{
while (node != null) {
System.out.print(node.data1 + " ");
node = node.nex;
}
}
//Main method is called which prints the reversed linked list by calling the function
public static void main(String[] args)
{
//The values to be inserted in the list before reversing are given here
List list = new List();
list.head1 = new Node(20);
list.head1.nex = new Node(30);
list.head1.nex.nex = new Node(40);
list.head1.nex.nex.nex = new Node(50);
System.out.println("The items in the linked list that needs to be reversed are");
list.printL(head1);
//Function to reverse the list is called here
Node result = list.reverse(head1, null);
System.out.println("");
System.out.println("");
System.out.println("The items in the reversed linked list are");
list.printL(result);
}
}

Output:

Conclusion

In this tutorial, we understand the concept of reversing the linked list through definition, the logic on which the linked list is reversed is explained. The two algorithms to reverse the linked list are explained, which is an iterative algorithm, and the recursive algorithm is explained along with the programming examples to implement the algorithms in java.

The above is the detailed content of Reverse Linked List in Java. For more information, please follow other related articles on the PHP Chinese website!