Table of contents
1.
Introduction 
2.
Reverse a Linked List Using Iterative Approach
3.
Reverse a Linked List Recursive Approach
4.
Reverse a Linked List Using Stack
4.1.
Java
5.
Frequently Asked Questions
5.1.
What are the key advantages of using a linked list over an array?
5.2.
What are the risks of modifying a linked list while reversing it?
5.3.
What is the difference between iterative and recursive approaches to reversing a linked list?
5.4.
What is the time complexity of the approach we have used to reverse the Linked List?
6.
Conclusion
Last Updated: Jan 7, 2025
Medium

Java Program to Reverse a Linked List

Author NISHANT RANA
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction 

Reversing a linked list is a common problem in data structures and algorithms, often asked in technical interviews to test one’s understanding of pointers and data manipulation. In Java, reversing a linked list requires adjusting the nodes’ links, which involves a different approach compared to working with arrays. This blog will walk you through multiple methods to reverse a linked list in Java.

Reverse a Linked List in Java

Input 1: 

1 -> 2 -> 3 -> 4 -> 5 -> NULL

 

Output 1:

NULL <- 1 <- 2 <- 3 <- 4 <- 5

 

Input 2:

1 -> NULL

 

Output 2:

1 -> NULL

Recommended: Do try the Problem yourself before moving on to the solution

Reverse a Linked List Using Iterative Approach

We will first discuss the Iterative Approach to reverse the Linked List. We will be maintaining the following three pointers:-

  1. current: This pointer will point to the current node we are at.
  2. prev: This pointer will point to the previous node of the current node. We will assume the previous of the Head node to be NULL.
  3. next: This pointer will point to the next of the current node.

 

We will use the prev pointer to update the next of the current node to be the previous node because this is what we will have when we reverse the Linked List.

 

We are maintaining the next pointer because once we update the next of the current node to be the previous node, we must have the access to the next of the current node to move to the next node.

 

Refer to the below implementation of the above approach.

Node reverse(Node head) {
    
    //Initializing our three pointers.
    Node prev = null;
    Node current = head;
    Node next = null;
    
    /*
      Running a for loop to 
      update the next pointer
      of all the nodes.
    */
    while (current != null) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    
    /*
      Last node is the head
      of the newly reversed
      Linked List
    */
    node = prev;
    return node;
}

 

Time Complexity: The time complexity for the above approach is O(N) (where ‘N’ is the number of nodes in the Linked List) because we are just iterating the Linked List once.

 

Space Complexity: The space complexity of the above approach is O(1) because we are using the constant auxiliary space.

 

Reverse a Linked List Recursive Approach

We will apply a similar approach to the Iterative Approach to reverse the Linked List using the prev, current, and next1 pointers. We will pass the current and the prev pointer to our recursive function. When we make a recursive call, we will pass the next node as the current node and the current node as the prev node.

 

Refer to the below implementation of the above approach.

Node reverse(Node curr, Node prev) {
  
        //Base case
        if (curr.next == null) {
            
            /*
              Updating the next 
              of the current node 
              to prev.
            */
            curr.next = prev;
            return curr;
        }
  
        /*
          Storing the next of 
          the current node for 
          the next recursive call
        */
        Node next1 = curr.next;
  
        /*
          Updating the next 
          of the current node 
          to prev.
        */
        curr.next = prev;
  
        return reverse(next1, curr);
}

 

Time Complexity: The time complexity for the above approach is O(N) (where N is the number of nodes in the Linked List) because we are just iterating the Linked List once.

 

Space Complexity: The space complexity of the above approach is O(1) because we are using the constant auxiliary space.

Check out this problem - Reverse Nodes In K Group
Must Read  C Program to Reverse a Number

Reverse a Linked List Using Stack

Using a stack to reverse a linked list is an intuitive approach. Here's the process in simple steps:

Push Nodes onto Stack:

  • Traverse through the linked list and push each node onto a stack. This way, the nodes are stored in reverse order (LIFO – Last In, First Out).

Pop Nodes from Stack:

  • Pop each node from the stack and reattach the nodes in this order to form the reversed linked list.

Reconstruct the List:

  • Set the head pointer to the first popped node.
  • Use a pointer to keep attaching each popped node to the next of the previous node until the stack is empty.
  • Finally, set the next pointer of the last node to null to mark the end of the list.

Implementation

  • Java

Java

import java.util.Stack;

class Node {
int data;
Node next;

Node(int data) {
this.data = data;
this.next = null;
}
}

class LinkedList {
Node head;

// Function to reverse the linked list using a stack
public void reverseUsingStack() {
Stack<Node> stack = new Stack<>();
Node temp = head;

// Push all nodes onto the stack
while (temp != null) {
stack.push(temp);
temp = temp.next;
}

// Set head to the last element popped from stack
if (!stack.isEmpty()) {
head = stack.pop();
temp = head;
}

// Pop nodes from the stack and reattach
while (!stack.isEmpty()) {
temp.next = stack.pop();
temp = temp.next;
}
temp.next = null; // Set the last node's next to null
}

// Helper method to print the linked list
public void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}

// Helper method to add a new node at the beginning
public void push(int data) {
Node newNode = new Node(data);
newNode.next = head;
head = newNode;
}
}

public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();

// Adding elements to the linked list
list.push(5);
list.push(4);
list.push(3);
list.push(2);
list.push(1);

System.out.println("Original Linked List:");
list.printList();

// Reverse the linked list using a stack
list.reverseUsingStack();

System.out.println("Reversed Linked List:");
list.printList();
}
}
You can also try this code with Online Java Compiler
Run Code

 

Output

Original Linked List:
1 2 3 4 5 
Reversed Linked List:
5 4 3 2 1

Frequently Asked Questions

What are the key advantages of using a linked list over an array?

Linked lists offer dynamic memory allocation, allowing efficient insertion and deletion without needing to shift elements, unlike arrays. They use memory more efficiently, especially for large datasets, as they don't require pre-defined sizing and can grow as needed.

What are the risks of modifying a linked list while reversing it?

Modifying a linked list during reversal risks losing node references if not handled carefully, especially with pointer manipulation. A single error can break the chain, potentially making the list unrecoverable. Ensuring safe pointer reassignment is essential to prevent data loss.

What is the difference between iterative and recursive approaches to reversing a linked list?

The iterative approach uses a loop to reverse node links one by one, saving memory and being easier to follow. The recursive approach involves function calls to process each node, which can be elegant but consumes more stack space, risking overflow for very large lists.

What is the time complexity of the approach we have used to reverse the Linked List?

The time complexity for the approach to reverse the Linked List is O(N) (where N is the number of nodes in the Linked List) because we are just iterating the Linked List once.

Conclusion

In this blog, we have covered Reverse a Linked List in Java. Reversing a linked list is a fundamental operation that demonstrates a deep understanding of data structures in Java. Whether using an iterative approach, a recursive method, or even a stack, each technique has its own advantages and trade-offs. Mastering these approaches not only strengthens problem-solving skills but also builds a foundation for tackling more advanced data structure challenges. 

If you want to learn more about Linked List and want to practice some questions which require you to take your basic knowledge on Linked List a notch higher, then you can visit our Guided Path for Linked List. To practice this problem, you can visit Practice Problem.

Recommended Reading:

Live masterclass