How to reverse a singly linked list in Java without recursion? Iterative Solution Example

Hello guys, reverse a linked list is a common coding problem from Programming Job interviews and I am sure you have seen this in your career, if you are not, maybe you are a fresher and you will going to find about this very soon in your next technical interview. In the last article, I have shown you how to use recursion to reverse a linked list, and today, I'll show you how to reverse a singly linked list in Java without recursion. A singly linked list, also known as just linked list is a collection of nodes that can only be traversed in one direction like in the forward direction from head to tail. Each node in the linked list contains two things, data and a pointer to the next node in the list.

In order to reverse the linked list, you need to iterate through the list, and at each step, we need to reverse the link like after the first iteration head will point to null and the next element will point to the head.

At the end of traversal when you reach the tail of the linked list, the tail will point to the second last element and it will become a new head because you can now traverse through all elements from this node.

Since we cannot use the java.util.LinkedList class to demonstrate this example, as it is a doubly-linked list and also in most of the time on coding interviews, the Interviewer will not allow you to use existing Java classes or API.

Anyway,  in a doubly-linked list, you can traverse in both directions like both forward and backward as each node contains the reference to both the previous and next node.

Btw, if you are not familiar with the linked list data structure, it's better to first go through a  good data structure and algorithm course like Data Structures and Algorithms: Deep Dive Using Java to learn more about linked lists data structure.

Implementing Your Own Linked List on Interviews

Since using existing Java classes is now allowed on Programming Job interviews, you need to create your own to write code. For this example, I have created our own singly linked list class. Similar to java.util.LinkedList also contains a nested static class Node, which represents a node in the linked list.

This class contains an integer attribute to hold the data part and another Node reference to point to the next one in the list. If you want to create a Generic linked list, you should replace int with T, a generic type, as shown here.

In order to demonstrate that our reverse method is working, we will not only have to create a linked list but also need to populate the linked list. In order to populate, you need to implement the add() method on the singly linked list.

You have two choices, either add the element at the head or at the tail, adding an element to the head is easy as it doesn't require a traversal till the end but if you want to create a list that contains elements in the order they are added then we need to add nodes at the end of the linked list.

I have also created a print() method to print all nodes of the singly linked list, separated by space. This method is very useful to demonstrate that our reverse method is actually working or not, as you can print the linked list before and after reversal.

If you struggle with implementing essential data structures like a linked list, binary tree, the hash table in your own code on any programming language like Java then I suggest you join Algorithms and Data Structures - Part 1 and 2 courses on Pluralsight. They will not only help you to write your data structure but also how to calculate time and space complexity.

Java Program to Reverse a singly linked list without Recursion

Here is our sample program to demonstrate how to reverse a linked list in Java. In order to reverse, I have first created a class called SinglyLinkedList, which represents a linked list data structure. I have further implemented add() and print() method to add elements to the linked list and print them in forwarding order.

The logic of reversing the linked list is encapsulated inside the reverse() method. It traverses through the linked list from head to tail and reverses the link in each step like each node instead of pointing to the next element started pointing to the previous node, this way the whole linked list is reversed when you reach the last element, which then becomes the new head of a linked list.

Here is a nice diagram that explains the algorithm to reverse a linked list without recursion in Java:

You can see that links are reversed in each step using the pointer's previous and next. This is also known as the iterative algorithm to reverse the linked list in Java. For the recursive algorithm, you can also see Introduction to Algorithms book by Thomas H. Cormen.

package test;

/**
 * Java Program to reverse a singly list without using recursion.
 */
public class LinkedListProblem {

  public static void main(String[] args) {

    // creating a singly linked list
    SinglyLinkedList.Node head = new SinglyLinkedList.Node(1);
    SinglyLinkedList linkedlist = new SinglyLinkedList(head);

    // adding node into singly linked list
    linkedlist.add(new SinglyLinkedList.Node(2));
    linkedlist.add(new SinglyLinkedList.Node(3));
    // printing a singly linked list
    linkedlist.print();

    // reversing the singly linked list
    linkedlist.reverse();

    // printing the singly linked list again
    linkedlist.print();

  }

}
/**
 * A class to represent singly list in Java
 * 
 * @author WINDOWS 8
 *
 */
class SinglyLinkedList {

  static class Node {

    private int data;
    private Node next;

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

    public int data() {
      return data;
    }

    public Node next() {
      return next;
    }
  }

  private Node head;

  public SinglyLinkedList(Node head) {
    this.head = head;
  }

  /**
   * Java method to add an element to linked list
   * @param node
   */
  public void add(Node node) {
    Node current = head;
    while (current != null) {
      if (current.next == null) {
        current.next = node;
        break;
      }
      current = current.next;
    }
  }

  /**
   * Java method to print a singly linked list
   */
  public void print() {
    Node node = head;
    while (node != null) {
      System.out.print(node.data() + " ");
      node = node.next();
    }
    System.out.println("");
  }

  /**
   * Java method to reverse a linked list without recursion
   */
  public void reverse() {
    Node pointer = head;
    Node previous = null, current = null;

    while (pointer != null) {
      current = pointer;
      pointer = pointer.next;

      // reverse the link
      current.next = previous;
      previous = current;
      head = current;
    }

  }
}
Output
1 2 3 
3 2 1 

You can see that the linked list has reversed, earlier 1 was the first element now it is last and 3 is the first element of the linked list or head.


That's all about how to reverse a singly linked list in Java without using recursion. Yes, we have not used recursion in this solution, instead, we have used iteration. You can see the while loop inside the reverse() method. 

Btw, if you get this question asked in the real interview, you would be most likely asked to reverse the linked list using recursion now. So, wait for another article to see that solution or check out the Cracking the Coding Interview book, which contains a solution to this problem along with several others.


Related Data Structure and Algorithm Interview Questions from Javarevisited Blog

• How to find the middle element of the linked list using a single pass? (solution)
• 10 Free courses to learn Data Structure and Algorithms (courses)
• How to find the 3rd element from the end of a linked list in Java? (solution)
• 7 Free Books to learn Data Structure and Algorithms (books)
• Top 15 Data Structure and Algorithm Interview Questions (see here)
• Top 20 String coding interview questions (see here)
• When to use ArrayList vs LinkedList in Java? (answer)
• 20+ linked list interview questions for programmers (questions)
• How to find if a singly linked list contains a loop? (solution)
• 7 Best Courses to learn Data Structure for Beginners (best courses)
• How to find the first and last element of a linked list in Java? (solution)
• How to convert a linked list to an array in Java? (example)
• How to search elements inside a linked list in Java? (solution)
• What is the difference between LinkedList and ArrayList in Java? (answer)
• Top 30 Array Coding Interview Questions with Answers (see here)
• Top 30 linked list coding interview questions (see here)
• Top 50 Java Programs from Coding Interviews (see here)
• 5 Free Data Structure and Algorithms Courses for Programmers (courses)
• 10 Algorithms Books Every Programmer Should Read (books)
• 50+ Data Structure and Algorithms Problems from Interviews (questions)
• 10 Free Data Structure and Algorithm Courses for Programmers (courses)
• 100+ Data Structure Coding Problems from Interviews (questions)

Thanks for reading this article so far. If you like this article then please share it with your friends and colleagues. If you have any questions or doubt then please let us know and I'll try to find an answer for you. As always suggestions, comments, innovative and better answers are most welcome.


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 these free data structure and algorithms courses on Udemy.