How to Reverse Linked List in Java? | Iterative and Recursive approach

Reverse Linked List (LL) using Iterative (While loop) and Recursive approach in Java

In this article, we will seen both Recursive and Iterative approach for reversing Singly linked list with explanation.   

First we store data (value and next node reference) in LinkedList custom class one by one. and then reverse it using loop. 

For reversing linked list data, we do not need to swap any elements we just need to change next data for particular Node. 

Lets jump to code for better understanding.

Example 1 : Iterative (Loop) approach for reverse Linked List

class Node {    
    int data;    
    Node next;     

    // Constructor for initialize data
    public Node (int data) {    
        this.data = data;    
        this.next = null;    
    }    
}  

public class ReverseLLByIterative {    
    
    public static Node head = null;    
    public Node tail = null;  
        
    public void addNode(int data) {    

        Node newNode = new Node(data);   
            
        if (head == null) {    
            head = newNode;    
            tail = newNode;    
        } else {    
            tail.next = newNode;    
            tail = newNode;    
        }    
    }    
    
    Node reverseLL(Node head) {
        Node current = head;
        Node previous = null;
       
        while (current != null) {
            Node temp = current.next;
            current.next = previous;
            previous = current;
            current = temp;
        }
        return previous;
    }
    
    void printLinkedList(Node head) {
        Node current = head;   
        
        while(current != null) {    
            System.out.print(current.data + " ");    
            current = current.next;    
        }    
    }   
        
    public static void main(String[] args) {    
            
        ReverseLLByIterative obj = new ReverseLLByIterative();    
            
        obj.addNode(1);    
        obj.addNode(2);    
        obj.addNode(3);    
        obj.addNode(4);  
        obj.addNode(5);
        obj.addNode(6);
        
        System.out.println("Linked list before Reverse : ");  
        obj.printLinkedList(head);
        
        head = obj.reverseLL(head);
        System.out.println("\nLinked list after Reverse : ");  
        obj.printLinkedList(head);
    }
}   

Output :

Linked list before Reverse :
1 2 3 4 5 6
Linked list after Reverse :
6 5 4 3 2 1 

Code Explanation :

• In Node class, declare two variables 1. int data and 2. Node next. data stores our values and next stores next reference Node.
• In ReverseLLByIterative, we are adding new Node using addNode() method. For that we are passing int data. In addNode(), creating object of Node class and store data and next reference.
• In reverseLL(), initialize current as head and previous Node as null.
• Loop until current is not null (means we are at last Node. in our example 6 is last Node data).
• First store next data of current to temp Node, so after deleting next reference we still have next Node.
• Store previous Node to current Node. So first node refer NULL value. ( NULL , <- 1  2-> 3 -> 4 ->5 -> 6). Now current refers to NULL value rather than 2 Node.
  
• Store previous Node to current and temp to current.
• Return previous (It is first node after reversing).
• In printLinkedList(), print all node values one by one.

 

Example 2 : Recursive approach for reverse Linked List

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

public class ReverseLLByRecursive {

     public static Node head = null;    
        public Node tail = null;  
            
        public void addNode(int data) {    

            Node newNode = new Node(data);    
                
            if(head == null) {    
                head = newNode;    
                tail = newNode;    
            } else {    
                tail.next = newNode;    
                tail = newNode;    
            }    
        }   
        
        Node reverseLL(Node head) {
            
            if (head == null || head.next == null) {
                return head;
            }
            
            Node secondElement = head.next;
            head.next = null;
            Node newHead = reverseLL(secondElement);
            secondElement.next = head;
            return newHead;
        }
        
        void printLinkedList(Node head) {
            Node current = head;   
            
            while(current != null) {    
                System.out.print(current.data + " ");    
                current = current.next;    
            }    
        }   
    
    public static void main(String[] args) {
        
        ReverseLLByRecursive obj = new ReverseLLByRecursive();    
        
        obj.addNode(1);    
        obj.addNode(2);    
        obj.addNode(3);    
        obj.addNode(4);  
        obj.addNode(5);
        obj.addNode(6);
        
        System.out.println("Linked list before Reverse : ");  
        obj.printLinkedList(head);
        
        head = obj.reverseLL(head);
        System.out.println("\nLinked list after Reverse : ");  
        obj.printLinkedList(head);

    }
}

Code explanation :

• In reverseLL() method, first check for null condition for head and head.next.
• After we are storing head.next value to secondElement Node and store null to that (we are deleting reference).
• Next call is recursion and it continue till it return null.
  
• After recursion, we got newHead as last Node (6) and head as (5) and it done reverse for us like 6 -> 5 -> 4 -> 3 -> 2 -> 1 
  

 

Other articles you may like :

• Read PDF and Write into Text file in Java
  
• Calling 3rd party API in Java using HttpURLConnection