Last Updated on June 19, 2024 by Abhishek Sharma
Reversing a linked list is a common problem in computer science and programming that involves changing the direction of the pointers in a linked list so that the last node becomes the first node, the second-to-last node becomes the second node, and so on. This problem is frequently used in technical interviews to test a candidate’s understanding of linked lists and their ability to manipulate pointers. In this article, we will explore how to reverse a linked list in Java, including the steps involved and the implementation details.
Problem Statement
In this question, we are given a singly linked list. We have to reverse the given list.
Problem Statement Understanding
Let’s try to understand this problem statement with help of examples.
Suppose the given linked list is:
Here we have to reverse this linked list. So to reverse the linked list, we will have to change the links of all the nodes of linked list such that:
- 1→7 will become 7→1.
- 7→15 becomes 15→7.
- 15→27 becomes 27→15.
27 will now become the new head of the linked list. So, the final reverse linked list will be
Input:
Output:
Explanation: The input list has been reversed.
This question is not a very complex one. We have to make use of list traversal in the question. The only change will be that we will be changing the links of each node.
Approach (Iterative)
The approach is going to be pretty simple:
- Create two nodes, say, prev and current.
- prev will initially point to null and the current will point to the head of the list.
- Now, we have to traverse through the list till the current becomes null.
- For every node, we are going to store the next of current in next and then will make the next of current point to prev. Finally we will make prev equal to current, and current equal to next.
By performing the above operations, we are changing the links of every node and ultimately reversing the list.
Algorithm
- Create two nodes – prev and current.
- The prev will initially point to null and current will point to head.
- Traverse through the list till current becomes null.
- Store the next of current in next.
- Now, make next of current point to prev.
- After pointing to previous, we will make the prev equal to the current, and current equal to the next.
- In the end, after the full traversal, the prev will be our head.
Dry Run
Code Implementation
public class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
Node reverse(Node node) {
Node prev = null;
Node current = node;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}
void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.head = new Node(1);
list.head.next = new Node(7);
list.head.next.next = new Node(15);
list.head.next.next.next = new Node(27);
System.out.println("Given Linked list");
list.printList(head);
head = list.reverse(head);
System.out.println("");
System.out.println("Reversed linked list ");
list.printList(head);
}
}
Output
Original Linked list
1 7 15 27
Reversed linked list
27 15 7 1
Time Complexity : O(n), as list traversal is needed.
Space Complexity : O(1), as only temporary variables are being created.
Approach (Recursive)
The recursive approach is going to be very much similar to the iterative approach.
- If the current node is the last, then we will mark it as our head, and it will now point to the prev node.
- If the base case fails, we will store the next of current in temp, and make the current point to the previous node. After doing this, we will recur with next as current, and current as previous.
By performing the above operations, we are changing the links of every node and ultimately reversing the list.
Algorithm
- Base case – If the current node is the last, make it the head and also make next of curr point to the prev.
- Save the next of current in next1.
- Now, make the next of the current point to the prev.
- Recur with next1 as curr and curr as prev.
Finally, return the head.
Dry Run
Code Implementation
public class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
Node reverseUtil(Node curr, Node prev) {
if (curr.next == null) {
head = curr;
curr.next = prev;
return null;
}
Node next1 = curr.next;
curr.next = prev;
reverseUtil(next1, curr);
return head;
}
void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
list.head = new Node(1);
list.head.next = new Node(7);
list.head.next.next = new Node(15);
list.head.next.next.next = new Node(27);
System.out.println("Original Linked list ");
list.printList(head);
Node res = list.reverseUtil(head, null);
System.out.println("");
System.out.println("");
System.out.println("Reversed linked list ");
list.printList(res);
}
}
Output
Original Linked list
1 7 15 27
Reversed linked list
27 15 7 1
Time Complexity : O(n), as list traversal is needed.
[forminator_quiz id=”4037″]
Reversing a linked list is an essential skill for any programmer, especially those working with data structures and algorithms. By understanding how to manipulate the pointers in a linked list, you can solve a variety of related problems efficiently. The Java implementation provided here demonstrates a straightforward approach to reversing a linked list using an iterative method. With practice, you can master this fundamental technique and apply it to more complex scenarios in your programming career. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.
FAQs on Java Program to Reverse a Linked List
Here are some FAQs related to Java Program to Reverse a Linked List:
Q1: What is a linked list?
A linked list is a linear data structure where each element, known as a node, contains a data part and a reference (or link) to the next node in the sequence. Linked lists are dynamic in size and allow for efficient insertion and deletion of elements.
Q2: Why would you want to reverse a linked list?
Reversing a linked list can be useful in various applications, such as undo operations in applications, stack implementations, and certain algorithmic problems where the order of elements needs to be reversed.
Q3: What are the common methods to reverse a linked list in Java?
The two common methods to reverse a linked list in Java are:
- Iterative Method: Using a loop to reverse the direction of the pointers.
- Recursive Method: Recursively reversing the pointers until the base case is reached.
Q4: How does the iterative method work for reversing a linked list?
The iterative method involves three pointers: prev, current, and next. The prev pointer is initialized to null, the current pointer is initialized to the head of the list, and the next pointer is used to temporarily store the next node. In each iteration, the current node’s next pointer is updated to point to prev, effectively reversing the link. The prev and current pointers are then moved one step forward until current becomes null.
Other Java Programs
Java program to find the factorial of a number
Java program to search an element in a linked list
Java program to convert arraylist to linkedlist
Java program to add two numbers