Reverse a Linked List in Java

This is a famous question in coding interviews. It looks simple, but it is actually not. Many devs struggle with this question.

For this question, we need to use our own LinkedList class and not the built-in class from java.util package.

And that is a singly-linked list.

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.

There are three ways we can reverse a Linked List in Java:

1. Iterative
2. Recursion
3. With Stack (least popular)

In most interviews, you'll be asked to reverse a Linked List in both an iterative and recursive manner.

Note: We are using the Linked List class we have already created here.

Reverse a Linked List - iterative

Here is an iterative solution, where we are using a while loop, and as long as the current node is not null, we are changing the pointers and moving them through the list.

public void reverseIterative() {
    Node<Integer> current = head;
    Node<Integer> next;
    Node<Integer> previous = null;

    while (current != null) {
        next = current.next;
        current.next = previous;
        previous = current;
        current = next;
    }

    head = previous;
}

Here, 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.

We have added the method inside the LinkedList class, so the value of the head node is accessible since it is an instance variable.

Reverse a Linked List - recursive

Here is the recursive solution:

public void reverse() {
    head = reverseRecursive(null, head); // setting the head to the new head (the last element)
}

private Node<T> reverseRecursive(Node<T> prevNode, Node<T> currentNode) {
    if (currentNode == null)
        return prevNode;
    Node<T> nextNode = currentNode.next;
    currentNode.next = prevNode;
    return reverseRecursive(currentNode, nextNode);
}

Here, we have exposed the reverse() method, and internally we are calling the method reverseRecursive passing the null as a previous node and a head node.

Reverse a Linked List using Stack

This is the least popular solution since we are not actually reversing the list itself, we are just adding the elements to the stack and then popping from the stack in reverse order.

public void reverseWithStack(LinkedList<Integer> linkedList) {
    Stack<Node<Integer>> stack = new Stack<>();
    Node<Integer> current = linkedList.head;

    while (current != null) {
        stack.push(current);
        current = current.next;
    }

    while (!stack.isEmpty()) {
        System.out.println(stack.pop().data);
    }
}

And that is all about how to reverse a Linked List in Java.