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

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 which 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, a 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 first iteration head will point to null and next element will point to 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 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 list data structure.





Implementing Your Own Linked List on Interviews

Since using existing Java classes are 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 which 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 element to head is easy as it doesn't require a traversal till the end but if you want to create a list which contains elements in the order they are added then we need to add nodes at the end of 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 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.

How to Reverse a Singly linked list without Recursion in Java? Coding Problem with Solution




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 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 which explains the algorithm to reverse a linked list without recursion in Java:



You can see that links are reverse in each steps using the pointers 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 linked list has reversed, earlier 1 was the first element now it is last and 3 is the first element of 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.

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


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)
  • How to find the 3rd element from the end of a linked list in Java? (solution)
  • 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)
  • How to find if a singly linked list contains a loop? (solution)
  • 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 element 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 with your friends and colleagues. If you have any question 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.

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

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.

No comments:

Post a Comment