How to reverse a linked list in Java using Recursion and Iteration (Loop) - Example

This is one of the class coding problems from Programming job interviews. It may seem easy to reverse a linked list but when you go around doing the actual task, it's not that easy, especially for first-timers. There are a couple of algorithms exists to reverse a singly linked list in Java, like you can use the three-pointers approach or solve this problem using a Stack, or simply using Recursion without the external stack. As I had pointed out in the earlier post about the linked list, that reversing a linked list is one of the most popular linked list-based data structure interview question. This means, you just can't afford to prepare this one, before going for any programming interview. Despite being so common, It's not easy to solve this problem on the fly.

Many Java programmers struggle to reverse a linked list using both recursion and iteration, which makes this question very useful for filtering programmers who can code and who are not so good with coding.

Indeed, this is one of the confusing algorithms to understand and it's not easy to grasp, especially if you haven't practiced linked list based questions like finding middle node of linked list in one pass or inserting and removing an element from the linked list data structure.

Since Java programmer gets a linked list implementation in the form of the java.util.LinkedList, they never bother to do this exercise by hand. Yes, there are some exceptions but many Java programmer doesn't focus enough on data structure and hand-coding, which is really important to improve your problem-solving skills for the interview.

So, when it comes to design a whole system using Object-oriented analysis and design like implementing a vending machine in Java, sometimes they fail to choose the correct data structure and devising simple algorithms.

Before going for a programming/coding interview, It's absolutely necessary to do as much practice in data structure and algorithm as possible to take advantage of all the knowledge available. You can also join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.

This will improve your thinking ability, problem-solving skill and you will be more comfortable with dealing with the unknown set of problems. This advice is irrespective of whether you are a Java, C++, or Python developer.

Java Program to Reverse a singly linked list using recursion and Iteration

A linked list is a data structure which contains nodes, every node keep data and pointer to the next node. This way linked list grows and can store as many elements as much memory allows it. It's not like an array that requires a contiguous chunk of memory because here node can be stored at any memory location.

This structure means, adding and removing elements in a linked list is easy but searching an element is expensive because you need to traverse the entire list to find the element. It doesn't help even if you know that element is the 5th node or 6th node because you cannot access them by index like an array.

This is the biggest difference between an array and a linked list data structure. In the array, searching the index is O(1) operation but in linked list searching is O(n) operation.

It is said that a picture is worth a thousand word and it is very true in the case of problem-solving and understanding algorithms. If you are a visual learner, I strongly suggest checking out the Visualizing Data Structures and Algorithms in Java course which explains all fundamental data structures and algorithms with animations and interesting diagrams.  Here are a diagram and a flowchart to reverse a singly linked list using recursion.

It divides the list into two parts first node and rest of the list, and then link rest to head in reverse order. It then recursively applies the same division until it reaches the last node, at that point whole linked list, is reversed.

Coming back to our code which represents a singly linked list in Java (see the next section), with limited operations. I have already removed some non-relevant code for performing different operations on a linked list like checking if the linked list is cyclic or not, inserting an element at the middle, and removing the element. Since we don't need this code for reversing a linked list, I have simply deleted them for now.

This class is similar to the SinglyLinkedList class, which we have seen in how to implement a linked list in Java using generics (see here), with two more methods for reversing linked list using iteration and recursion.

The reverseRecursively() method reverses the linked list using recursion. It uses the call stack to store data, and once we reached tail, which becomes the new head for the reversed linked list, it starts adding nodes in reverse order. Look at some comments around those methods, which will make you understand the algorithm of reversing the linked list better.

The reverseIteratively() method reverses the linked list using the three-pointers approach and using loops, that's why it is called an iterative solution. It traverses through the linked list and adding nodes at the beginning of the singly linked list in each iteration. It uses three reference variables (pointers) to keep track of previous, current, and next nodes.

Btw, If you are not very familiar with a linked list data structure or want to learn more about linked list data structure, you should first read a good course on data structure and algorithm like Algorithms and Data Structures - Part 1 and 2 on Pluralsight, one of the best course to learn data structure and algorithms.

Java Class to Represent Singly Linked List

Here is our Java program to solve this problem. As I said, it contains a class to represent a singly linked list and it contains another class that has the main method for testing. That class creates an instance of a linked list and then call relevant methods to reverse the linked list by using iteration and recursion. 

/**
  * Java Class to represent singly linked list for demonstration purpose.
  * In order to understand How to reverse linked list, focus on two methods
  * reverseIteratively() and reverseRecursively().

  * @author Javin Paul
  */
public class SinglyLinkedList {
    private Node head;  // Head is the first node in linked list

    public void append(T data){
        if(head == null){
            head = new Node(data);
            return;
        }
        tail().next = new Node(data);
    }
 
    private Node tail() {
        Node tail = head;
     
        // Find last element of linked list known as tail
        while(tail.next != null){
            tail = tail.next;
        }      
        return tail;
     
    }

 
    @Override
    public String toString(){
        StringBuilder sb = new StringBuilder();
        Node current = head;
        while(current != null){
           sb.append(current).append("-->");
           current = current.next;
        }    
        if(sb.length() >=3){
            sb.delete(sb.length() - 3, sb.length()); 
            // to remove --> from last node
        }
     
        return sb.toString();
    }

    /**
      * Reverse linked list using 3 pointers approach in O(n) time
      * It basically creates a new list by reversing direction, and
      * subsequently insert the element at the start of the list.
      */
    public void reverseIteratively() {
        Node current = head;
        Node previous = null;
        Node forward = null;
     
        // traversing linked list until there is no more element
        while(current.next != null){
         
            // Saving reference of next node, since we are changing current node
            forward = current.next;
         
            // Inserting node at start of new list
            current.next = previous;
            previous = current;
         
            // Advancing to next node
            current = forward;
        }
     
        head = current;
        head.next = previous;
    }
 
    /*
     * Reverse a singly linked list using recursion. In recursion Stack is
     * used to store data.   
     * 1. Traverse linked list till we find the tail, 
     * that would be new head for reversed linked list.
     */
    private Node reverseRecursively(Node node){
       Node newHead;
     
       //base case - tail of original linked list
       if((node.next == null)){
           return node;
       }
       newHead = reverseRecursively(node.next);
     
       //reverse the link e.g. C->D->null will be null       
       node.next.next = node;
       node.next = null;    
       return newHead;
    }
  
    public void reverseRecursively(){
        head = reverseRecursively(head);
    }  
 
   private static class Node {
        private Node next;
        private T data;

        public Node(T data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }
 
}

Test Class

Here is our test class, which will test both methods of reversing a linked list, reverseIteratively() and reverseRecursively(). You have first created a singly linked list with 6 nodes A-B-C-D-E-F and first reversed them iteratively using 3 points approach and later reversed the same list recursively.

Since the same instance of the singly linked list is reversed two times, you can see in the output that the final list is the same as the original linked list.

/**
  * Java program to test code of reversing singly linked list in Java.
  * This test class test both iterative and recursive solution. Since
  * the same list is first reversed using loops, and then again using recursion.
  * You can see that final output is same as original linked list.

  * @author Javin Paul
  */
public class SinglyLinkedListTest {

    public static void main(String args[]) {
       SinglyLinkedList linkedlist = getDefaultList();
       System.out.println("linked list before reversing : " + linkedlist);     
       linkedlist.reverseIteratively();     
       System.out.println("linked list after reversing : " + linkedlist);
       linkedlist.reverseRecursively();
       System.out.println("linked list after reversing recursively: "
                                   + linkedlist);
           
    }
  
     private static SinglyLinkedList getDefaultList(){
        SinglyLinkedList linkedlist = new SinglyLinkedList();       
        linkedlist.append("A"); linkedlist.append("B"); linkedlist.append("C");
        linkedlist.append("D"); linkedlist.append("E"); linkedlist.append("F");
        return linkedlist;
    }
  
}

Output:
linked list before reversing : A-->B-->C-->D-->E-->F
linked list after reversing : F-->E-->D-->C-->B-->A
linked list after reversing recursively: A-->B-->C-->D-->E-->F

That's all on how to reverse a linked list in Java. We have seen two approaches to reverse a singly linked list, first using Iterations, which involves 3 pointers or reference variable; and second, which reversed linked list using recursion.

The reason, I have shared both approaches because they are asked as a follow-up question, and it's always better to know both approaches to make a good impression.

By the way, if you can improve the algorithm, and can find a few more ways to reverse a linked list, it will always act as a plus point for you. You can also check out the following resources for more practice questions and improving your Data Structure and Algorithms:

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java: An Interview Refresher
Cracking the Coding Interview - 189 Questions and Solutions


Related linked list and data structure questions you may like to explore

• When to use ArrayList vs LinkedList in Java? (answer)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• How to convert a linked list to an array in Java? (example)
• How to find the first and last element of a linked list in Java? (solution)
• How to search elements inside a linked list in Java? (solution)
• What is the difference between LinkedList and ArrayList in Java? (answer)
• How to find a missing value from an array containing 1 to 100? (solution)
• How to reverse an array in place in Java? (solution)
• Top 30 Array-based Interview Questions for Programmers (list)
• My favorite free courses to learn data Structure in-depth (FreeCodeCamp)
• Top 5 Books to Learn Data Structure and Algorithms (books)
• How to count the number of leaf nodes in a given binary tree in Java? (solution)
• Top 5 Books for Programming and Coding Interviews (books)
• How to remove duplicates from an array in Java? (solution)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• Iterative PreOrder traversal in a binary tree (solution)
• Recursive InOrder traversal Algorithm (solution)
• 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If you like this Java Array tutorial then please share it with your friends and colleagues. If you have any questions or feedback then please drop a comment.


P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check the Easy to Advanced Data Structures course on Udemy. It's authored by a Google Software Engineer and Algorithm expert and its completely free of cost.

P.P. S. - Are you ready for the Interview? Take TripleByte's quiz and go directly to the final round of interviews with top tech companies like Coursera, Adobe, Dropbox, Grammarly, Uber, Quora, Evernote, Twitch, and many more.