How to reverse a LinkedList in Java

Hello people! today we are going to learn the concept of reversing a LinkedList in Java. Before we move to learn how to reverse a LinkedList in Java, let me tell you that LinkedList is a data structure where every data element is in the form of a node and each node contains the address of the next node. This sets a link between both the nodes. There are various situations where the reverse of a LinkedList is required such as to check whether a LinkedList is a palindrome or not. There are several ways to reverse a LinkedList. Today we are going to learn one of them.

How to reverse a LinkedList in Java

Let’s look at the solution, here we will traverse every node and change the direction of the link of every node which is pointing to a forward node. we will make it point to the previous node. In this way, the first node will point to null and the last node will become the head of the LinkedList.

Original LinkedList:-                                                          After Reversing LinkedList:- 

head  ->4  ->5  ->8  ->9  ->null                                                null<- 4 <- 5 <- 8 <- 9 <- head

Here is the code for the same:-

import java.util.Scanner;
class Node {               
  int data;
  node next;

  node(int d) {
    data = d;
    next = null;
  }
}

public class reverse {
  Node head;

  void printlist(Node head)                       // function to print the LinkedList
  {
    Node temp = head;
    
    System.out.print("Head-> ");
    
    while (temp != null) {
      
      System.out.print(temp.data + "-> ");
      temp = temp.next;
    }
    
    System.out.println("NULL");
  }

  public void addToTheLast(Node node)     // add new node at the end of the LinkedList
  {
    if (head == null)
      head = node;
    else {
      Node temp = head;
      while (temp.next != null) {
        temp = temp.next;
      }
      temp.next = node;
    }
  }

  public static void main(String[] args)               //Main function
  
{
    
    Scanner sc = new Scanner(System.in);

    reverseClass llist2 = new reverseClass();          //object of class reverseClass
    System.out.println("Enter the size of linklist");
    int n = sc.nextInt();
    
    reverse llist1 = new reverse();                     //object of class reverse
    
    System.out.println("Enter the integer data in linklist");
    int a1 = sc.nextInt();
    Node head = new Node(a1);
    llist1.addToTheLast(head);                        // add head to linkedlist

    for (int i = 1; i < n; i++) {                      //add remaining nodes
      int a = sc.nextInt();
      llist1.addToTheLast(new Node(a));
    }
    System.out.println("Before reversing"); 
    llist1.printlist(head);

    Node head2 = null;
    System.out.println("After reversing");
    head2 = llist2.reverse(head);
    llist1.printlist(head2);

  }
}

class reverseClass {
  Node reverse(Node head)                // reverse function 
  {

    Node temp = head, prev = null, n = head.next;
    while (n != null) {

      temp.next = prev;                // changing link of node 
      prev = temp;
      temp = n;
      n = n.next;

    }
    temp.next = prev;
    head = temp;

    return head;
  }

}

Output:-

Enter the size of linklist
5
Enter the integer data in linklist
6
2
1
4
8
Before reversing
Head-> 6-> 2-> 1-> 4-> 8-> NULL
After reversing
Head-> 8-> 4-> 1-> 2-> 6-> NULL

The time complexity of the code:- O(n)

Because we are traversing each node only one time. we can also reverse a LinkedList without actually changing the links of the node. We can do so by using another data structure called Stack.

Hope you understand the code.

You may also read:

• How to find if Linked List contains cycle in Java