How to reverse a singly linked list in Java? Example

In this article, 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 e.g. forward. Each node in the linked list contains two things, a data and a pointer to next node in the list. In order to reverse the linked list, we need to iterate through the list and at each step we need to reverse the link e.g. 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 linked list, the tail will point to the second last element and it will become a new head because you can traverse through all elements from this node.

Since we cannot use java.util.LinkedList to demonstrate this example, as it is a doubly linked list. In doubly linked list you can traverse in both directions i.e. forward and backward as each node contains the reference to both previous and next node. See a good data structure and algorithm book like Introduction to Algorithms by Thomas H. Cormen to learn more about linked list data structure.

For this example, I have created our own singly linked list class. Similar to java.util.LinkedList it also contains a nested static class Node, which represents a node the linked list. This 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 to populate the linked list. In order to populate, we need to implement the add() method on 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 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.




Java Program to reverse 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 represent a linked list data structure. I have further implemented add() and print() method to add elements to the linked list and print them in forward 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 e.g. 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 linked list.

Here is a nice diagram which explains the algorithm to reverse 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, 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 reverse() method. Though, 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.

Other linked list tutorials for Java Programmers
  • 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 linked list in Java? (solution)
  • How to find middle element of linked list in one pass? (solution)
  • How to convert linked list to array in Java? (example)
  • How to search element inside linked list in Java? (solution)
  • What is the difference between LinkedList and ArrayList in Java? (answer)


No comments:

Post a Comment