Thursday, March 23, 2017

How to Reverse a linked list in Java using Recursion and Loops

There are a couple of algorithms exists to reverse a singly linked list in Java e.g. 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 on the earlier post about linked list, that reversing a linked list is one of the most popular data structure interview question, based on linked list, which 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 programmer struggles to reverse a linked list using both iteration and recursion, 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 e.g. finding middle node of linked list in one pass or inserting and removing an element from linked list data structure.

Since Java programmer gets a linked list implementation in the form of 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 e.g. 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. 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 next node. This way linked list grows and can store as many elements as much memory allows it. It's not like an array which requires a contiguous chunk of memory because here node can be stored at any memory location.

This structure means, adding and removing elements in linked list is easy but searching an element is expensive because you need to traverse 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 linked list data structure. In the array, searching the index is O(1) operation but in linked list searching is O(n) operation.

Below code represent a singly linked list in Java, with limited operations. I have already removed some non-relevant code for performing different operations on linked list i.e. checking if 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 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 linked list in Java using generics (see here), with two more methods for reversing linked list using iteration and recursion.

The reverseRecursively() method reverse the linked list using recursion. It uses the call stack to store data, and once we reached tail, which becomes 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 linked list better.

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. Here are a diagram and flowchart to reverse a singly linked list using recursion. It divides the list into two parts first node and rest of list, and then link rest to head in reverse order. It then recursively applies same division until it reaches the last node, at that point whole linked list, is reversed. 

How to Reverse a linked list in Java using Recursion and Loops


The reverseIteratively() method reverses linked list using the three-pointers approach and using loops, that's why it is called 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.

If you are not very familiar with linked list data structure or want to learn more about linked list data structure, you should first read a good book on data structure and algorithm e.g. Data Structures and Algorithms Made Easy in Java by Narasimha Karumanchi, one of the best books to learn data structure and algorithms.

How to Reverse a linked list in Java using Recursion


Java Class to represent Singly Linked List

Here is our Java program solve this problem. As I said, it contains a class to represent singly linked list and it contains another class which has the main method for testing. That class creates an instance of 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 linked list, reverseIteratively() and reverseRecursively(). We 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 final list is same as 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 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 few more ways to reverse linked list, will always act as plus point for you. You can also check out Cracking the code interview 6th Edition for more practice questions. It contains 189 coding interview questions based upon data structure, algorithms, and other topics.




Related linked list and data structure questions you may like to explore
  • When to use ArrayList vs LinkedList in Java? (answer)
  • How to convert linked list to an array in Java? (example)
  • How to find the first and last element of linked list in Java? (solution)
  • How to search element inside linked list in Java? (solution)
  • What is the difference between LinkedList and ArrayList in Java? (answer)
  • How to reverse an array in place in Java? (solution)
  • Top 30 Array-based Interview Questions for Programmers (list)
  • Top 5 Books to Learn Data Structure and Algorithms (books)
  • Top 5 Books for Programming and Coding Interviews (books)

Further Reading
Algorithms and Data Structures - Part 1
Algorithms and Data Structures - Part 2

Thanks for reading this interview question. If you like this article then please share with your friends and colleagues. If you have any suggestions or feedback then please share your comment.

3 comments :

Common Man Protection Force said...

hey you are wrong, we can access thru the index

public class LinkedListDemo {

public static void main(String[] args) {

// create a LinkedList
LinkedList list = new LinkedList();

// add some elements
list.add("Hello");
list.add(2);
list.add("Chocolate");
list.add("10");

// print the list
System.out.println("LinkedList:" + list);

// print element at index 3
System.out.println("Element at index 3 :" + list.get(3));
}
}

Bhagyashree Dhavalshankh said...

Thank you for illustration.

Unknown said...

@Common man protection force,

Linkedlist API is provided with index based access but it doesn't work like array, if you check internal logic of get(index) method, you will find, internally Linkedlist iterate through each element upto index

But in case of array, you can directly go to specific index.

Post a Comment