How to Reverse a Linked List in Java

In this post we’ll see a Java program to reverse a linked list.

Reversing a linked list

Linked list data structure as we know contains node where each node refers to the next node. That’s how each node of the linked list can be reached even if nodes are not stored in contiguous memory. If we have to reverse a linked list “previous node refers the next node” should be reversed and the next node should point to the previous node instead.

As you can see apart from changing the references to the next node, head should also be changed so that it points to the first node after the reversal of the linked list.

Java program to reverse a linked list can be written using both-

Iterative approach. See example.
Recursive approach. See example.

Java program to reverse a linked list - Iterative

For the Java program to reverse a linked list using iterative method you need three instances of Node- previous, current and next. As the names suggest current points to the current node in the iteration, previous points to the node on the left of the current node (null when current points to first node) and next points to the node on the right of the current node.

Iterate the linked list until current is null. In each iteration-

next = current.next;
// that’s where reference is reversed
current.next = previous; 

// Move forward by one node
previous = current;
current = next;

Following image shows how it works using three nodes.

Java code

public class LinkedListReversal {
 private Node head;
 LinkedListReversal(){
  head = null;
 }
 static class Node{
  //data
  int i;
  Node next;
  Node(int i){
   this.i = i;
   this.next = null;
  }
  public void displayData(){
   System.out.print(" " + i);
  }
 }
 // Method to add nodes to linked list
 public void insertLast(Node newNode){
  if(isEmpty()){
   head = newNode;
  }else{
   Node current = head;
   // traverse to the last of the list
   while(current.next != null){
    current = current.next;
   }
   // adding new node, current last node
   // starts referencing to this new node
   current.next = newNode;
  }
 }
 public boolean isEmpty(){
  return head == null;
 }
 //Method for reversing linked list
 public void reverseList(){
  Node previous = null;
  Node current = head;
  Node next;
  while(current != null){
   next = current.next;
   // that’s where reference is reversed
   current.next = previous; 
   // Move forward by one node
   previous = current;
   current = next;
  }
  // By the end of traversal previous is at the 
  // last node which becomes the head after reversal
  head = previous;
 }
 // Method to traverse and display all nodes
 public void displayList(){
  Node current = head;
  while(current != null){
   current.displayData();
   current = current.next;
  }
 }
 public static void main(String[] args) {
  LinkedListReversal list = new LinkedListReversal();
  list.insertLast(new Node(10));
  list.insertLast(new Node(20));
  list.insertLast(new Node(30));
  list.insertLast(new Node(40));
  list.insertLast(new Node(50));
  System.out.println("Original linked list");
  list.displayList();
  list.reverseList();
  System.out.println("");
  System.out.println("Reversed linked list");
  list.displayList();
 }
}

Output

Original linked list
 10 20 30 40 50
Reversed linked list
 50 40 30 20 10

Java program to reverse a linked list – Recursive

In the recursive method for reversing a linked list method is called passing the first node then the method is recursively called by passing the next node (node.next).

Base case is when node.next is null.

public class LinkedListReversal {
 private Node head;
 LinkedListReversal(){
  head = null;
 }
 static class Node{
  //data
  int i;
  Node next;
  Node(int i){
   this.i = i;
   this.next = null;
  }
  public void displayData(){
   System.out.print(" " + i);
  }
 }
 // Method to add nodes to linked list
 public void insertLast(Node newNode){
  if(isEmpty()){
   head = newNode;
  }else{
   Node current = head;
   // traverse to the last of the list
   while(current.next != null){
    current = current.next;
   }
   // adding new node, current last node
   // starts referencing to this new node
   current.next = newNode;
  }
 }
 public boolean isEmpty(){
  return head == null;
 }
 
 //Method for reversing linked list - recursive
 public Node reverseListRecursive(Node current){
  // base case
  if(current.next == null){
   return current;
  }
  Node node = reverseListRecursive(current.next);
  // that’s where reference is reversed
  current.next.next = current;
  current.next = null;
  return node;
 }
 // Method to traverse and display all nodes
 public void displayList(){
  Node current = head;
  while(current != null){
   current.displayData();
   current = current.next;
  }
 }
 public static void main(String[] args) {
  LinkedListReversal list = new LinkedListReversal();
  list.insertLast(new Node(10));
  list.insertLast(new Node(20));
  list.insertLast(new Node(30));
  list.insertLast(new Node(40));
  list.insertLast(new Node(50));
  System.out.println("Original linked list");
  list.displayList();
  Node node = list.reverseListRecursive(list.head);
  // change the head
  list.head = node;
  System.out.println("");
  System.out.println("Reversed linked list");
  list.displayList();
 }
}

Output

Original linked list
 10 20 30 40 50
Reversed linked list
 50 40 30 20 10

In the recursive method reference is reversed in the following line

current.next.next = current;

Following image tries to clarify what this line does.

That's all for this topic How to Reverse a Linked List in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Saturday, May 21, 2022