# 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.

## 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:

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:

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!