Reverse a Linked List

In this article, we will discuss 2 different ways to reverse a given linked list using an iterative and recursive way in Java. Reversing a linked list means reversing the pointer between the nodes but not the actual node data.

Given below a linked list and its corresponding reversed list.

Iterative Way

The iterative way requires 3 different pointers to reverse a given linked list and in each iteration the current node next pointer points back to the previous node. Assuming the current pointer starts with the head pointer and the previous pointer points to a NULL reference, after every iteration, the current pointer starts pointing to the previous pointer and then move previous and current pointer one step ahead.

The iterative way follows the below algorithm.

1. Initialize three pointers prev as NULL, current as head, and next as NULL.
2. Iterate the list until the tail node is reached i.e. current node is null and repeat step 3, 4 and 5
3. Store current->next pointer to next node
4. Point current node next pointer to previous node
5. Move previous and current pointer one step ahead

Below is the Java code implementation. We are using the custom linked list implementation that we implemented in our last example.

public class Node {

    private int data;
    private Node nextNode;

//setters and getters

public Node reverse(){
        Node previous = null;
        Node current = head;
        Node next;
        while (current != null){
            next = current.getNextNode();
            current.setNextNode(previous);
            previous = current;
            current = next;
        }
        this.head = previous;
        return previous;
    }

Recursive Way

The recursive approach also reverses the linked list reference pointers rather then the values of the node. We have 2 base conditions for this.

First we recursively traverse the linked list untill we hit our base condition where current.getNextNode() == null then the current node next to next pointer starts pointing to the current node and this is the part where actual reversing of the node pointers happens.

 //Start with current pointer which initially points to the head node.
1. If current is NULL, return
2. If current->next is null then mark it as head node node and return
3. Point current->next->next to current //Actual reversal happens here
4. Set current->next to NULL

public Node reverseRecursively(Node current){
        if (current == null){
            return null;
        }
        if (current.getNextNode() == null){
            this.head= current;
            return current;
        }
        Node node = reverseRecursively(current.getNextNode());
        current.getNextNode().setNextNode(current);
        current.setNextNode(null);
        return node;
    }

Linked List Reverse Runner

public class LinkedListRunner {

    public static void main(String [] args){
        CustomLinkedList customLinkedList = new CustomLinkedList();
        customLinkedList.insert(5);
        customLinkedList.insert(10);
        customLinkedList.insert(15);
        customLinkedList.insert(20);
        
        customLinkedList.display();

        System.out.println("Going to reverse the list");
        customLinkedList.reverseRecursively();
        customLinkedList.display();
    }
}

Conclusion

In this article, we discussed 2 different ways to reverse a given linked list using an iterative and recursive way.