Reverse a Linked List in Java by Recursion

Overview

In this example we will see how to reverse a LinkedList in Java using recursion. In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence.

Figure 1. Linked List representation

Code

In this section we will see the working code example of reversing a linked list using recursion:

package com.zia.linkedlist;

public class ReverseLinkedListByRecursion {

    private Node head;

    public static Node reverseLinkedListUsingRecursion(Node currentNode) {
        ReverseLinkedListByRecursion obj = new ReverseLinkedListByRecursion();
        if (currentNode == null || currentNode.next == null) {
            return currentNode;
        }
        Node remaining = reverseLinkedListUsingRecursion(currentNode.next);
        currentNode.next.next = currentNode;
        currentNode.next = null;
        return remaining;
    }

    public void addToList(Node node) {
        if (head == null) {
            head = node;
        } else {
            Node temp = head;
            while (temp.next != null) {
                temp = temp.next;
            }
            temp.next = node;
        }
    }

    static class Node {
        private String data;
        private Node next;

        Node(String data) {
            this.data = data;
        }

        public String getData() {
            return data;
        }

        public Node getNext() {
            return next;
        }
    }
}

Test

Below is the test for the code above:

package com.zia.linkedlist;

import org.junit.Test;

import static org.junit.Assert.assertEquals;

public class ReverseLinkedListByRecursionTest {

    @Test
    public void testReverseLinkedListRecursion() {

        ReverseLinkedListByRecursion obj = new ReverseLinkedListByRecursion();
        ReverseLinkedListByRecursion.Node head = new ReverseLinkedListByRecursion.Node("Head");
        obj.addToList(head);
        obj.addToList(new ReverseLinkedListByRecursion.Node("First"));
        obj.addToList(new ReverseLinkedListByRecursion.Node("Second"));
        obj.addToList(new ReverseLinkedListByRecursion.Node("Third"));
        obj.addToList(new ReverseLinkedListByRecursion.Node("Fourth"));
        obj.addToList(new ReverseLinkedListByRecursion.Node("Fifth"));

        final ReverseLinkedListByRecursion.Node reverseLinkedList = ReverseLinkedListByRecursion.reverseLinkedListUsingRecursion(head);

        assertEquals(reverseLinkedList.getData(), "Fifth");
        assertEquals(reverseLinkedList.getNext().getData(), "Fourth");
        assertEquals(reverseLinkedList.getNext().getNext().getData(), "Third");
        assertEquals(reverseLinkedList.getNext().getNext().getNext().getData(), "Second");
        assertEquals(reverseLinkedList.getNext().getNext().getNext().getNext().getData(), "First");
        assertEquals(reverseLinkedList.getNext().getNext().getNext().getNext().getNext().getData(), "Head");
    }
}

Conclusion

In this example we saw how to reverse a linked list using recursion.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: