Atom
Atom's Cove

Atom's Cove

Reverse a Linked List in Java

Reverse a Linked List in Java

Learn how to reverse a linked list in Java. Don't worry, if you don't know Java, the algorithm will still apply to other languages.

Atom's photo
Atom
·May 7, 2022·

4 min read

Subscribe to my newsletter and never miss my upcoming articles

Table of contents

  • Linked Lists, what are they?
  • Iterative Algorithm Implementation
  • Recursive Algorithm Implementation
  • Conclusion

Linked Lists, what are they?

A linked list is a linear data structure in which a pointer in each element determines the order. Each element of a linked list contains a data field to store the list data and a pointer field to the next element in the sequence. Also, we can use a head pointer to point the start element of a linked list:

image.png

After we reverse the linked list, the head will point to the last element of the original linked list, and the pointer of each element will point to the previous element of the original linked list:

image.png

In Java, we have a LinkedList class to provide a double linked list implement of the List and Deque interfaces. However, we'll use a general single linked list data structure in this tutorial.

Let's first start with a ListNode class to represent an element of a linked list.

public class ListNode {
    private int data;
    private ListNode next;

    ListNode(int data) {
        this.data = data;
        this.next = null;
    }
}

The ListNode class has two fields:

  • An integer value to represent the data of the element
  • A pointer/reference to the next element

A linked list may contain multiple ListNode objects. For example, we can construct the above sample linked list with a loop:

ListNode constructLinkedList() {
    ListNode head = null;
    ListNode tail = null;
    for (int i = 1; i <= 5; i++) {
        ListNode node = new ListNode(i);
        if (head == null) {
            head = node;
        } else {
            tail.setNext(node);
        }
        tail = node;
    }
    return head;
}

Iterative Algorithm Implementation

Let's implement the iterative algorithm in Java:

ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    while (current != null) {
        ListNode nextElement = current.getNext();
        current.setNext(previous);
        previous = current;
        current = nextElement;
    }
    return previous;
}

In this iterative algorithm, we will use two ListNode variables, previous and current, to represent two adjacent elements in the linked list. For each iteration, we reverse these two elements and then shift to the next two elements.

In the end, the current pointer will be null, and the previous pointer will be the last element of the old linked list. Therefore, previous is also the new head pointer of the reversed linked list, and we return it from the method.

We can verify this iterative implementation with a simple unit test:

@Test
public void givenLinkedList_whenIterativeReverse_thenOutputCorrectResult() {
    ListNode head = constructLinkedList();
    ListNode node = head;
    for (int i = 1; i <= 5; i++) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }

    LinkedListReversal reversal = new LinkedListReversal();
    node = reversal.reverseList(head);

    for (int i = 5; i >= 1; i--) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
}

In this unit test, we first construct a sample linked list with five nodes. Also, we verify that each node in the linked list contains the correct data value. Then, we call the iterative function to reverse the linked list. Finally, we check the reversed linked list to make sure the data are reversed as expected.

Now, that's one way to do it. But let's think faster and more efficient. That brings us to the...

Recursive Algorithm Implementation

Now let's implement the recursive algorithm in Java:

ListNode reverseListRecursive(ListNode head) {
    if (head == null) {
        return null;
    }
    if (head.getNext() == null) {
        return head;
    }
    ListNode node = reverseListRecursive(head.getNext());
    head.getNext().setNext(head);
    head.setNext(null);
    return node;
}

In the reverseListRecursive function, we recursively visit each element in the linked list until we reach the last one. This last element will become the new head of the reverse linked list. Also, we append the visited element to the end of the partially reversed linked list.

Similarly, we can verify this recursive implementation with a simple unit test:

@Test
public void givenLinkedList_whenRecursiveReverse_thenOutputCorrectResult() {
    ListNode head = constructLinkedList();
    ListNode node = head;
    for (int i = 1; i <= 5; i++) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }

    LinkedListReversal reversal = new LinkedListReversal();
    node = reversal.reverseListRecursive(head);

    for (int i = 5; i >= 1; i--) {
        assertNotNull(node);
        assertEquals(i, node.getData());
        node = node.getNext();
    }
}

Conclusion

In this tutorial, we implemented two algorithms to reverse a linked list. Make sure to sign up for the newsletter for more helpful posts like this one. Goodbye, and have a nice day!

As always, if you have any questions, make sure to leave them in the comments and I will answer them as fast as I can!

 
Share this