 ## 1. Overview

In this tutorial, we're going to explain how to find the middle element of a linked list in Java.

We'll introduce the main problems in the next sections, and we'll show different approaches to solving them.

## 2. Keeping Track of the Size

This problem can be easily solved just by keeping track of the size when we add new elements to the list. If we know the size, we also know where the middle element is, so the solution is trivial.

Let's see an example using the Java implementation of a LinkedList:

``````public static Optional<String> findMiddleElementLinkedList(
return Optional.empty();
}

}``````

If we check the internal code of the LinkedList class, we can see that in this example we're just traversing the list till we reach the middle element:

``````Node<E> node(int index) {
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
return x;
}
}``````

## 3. Finding the Middle Without Knowing the Size

It's very common that we encounter problems where we only have the head node of a linked list, and we need to find the middle element. In this case, we don't know the size of the list, which makes this problem harder to solve.

We'll show in the next sections several approaches to solving this problem, but first, we need to create a class to represent a node of the list.

Let's create a Node class, which stores String values:

``````public static class Node {

private Node next;
private String data;

// constructors/getters/setters

public boolean hasNext() {
return next != null;
}

public void setNext(Node next) {
this.next = next;
}

public String toString() {
return this.data;
}
}``````

Also, we'll use this helper method in our test cases to create a singly linked list using only our nodes:

``````private static Node createNodesList(int n) {

for (int i = 2; i <= n; i++) {
Node newNode = new Node(String.valueOf(i));
current.setNext(newNode);
current = newNode;
}

}``````

### 3.1. Finding the Size First

The simplest approach to tackle this problem is to find the size of the list first, and after that follow the same approach that we used before – to iterate until the middle element.

Let's see this solution in action:

``````public static Optional<String> findMiddleElementFromHead(Node head) {
return Optional.empty();
}

// calculate the size of the list
int size = 1;
while (current.hasNext()) {
current = current.next();
size++;
}

// iterate till the middle element
for (int i = 0; i < (size - 1) / 2; i++) {
current = current.next();
}

return Optional.of(current.data());
}``````

As we can see, this code iterates through the list twice. Therefore, this solution has a poor performance and it's not recommended.

### 3.2. Finding the Middle Element in One Pass Iteratively

We're now going to improve the previous solution by finding the middle element with only one iteration over the list.

To do that iteratively, we need two pointers to iterate through the list at the same time. One pointer will advance 2 nodes in each iteration, and the other pointer will advance only one node per iteration.

When the faster pointer reaches the end of the list, the slower pointer will be in the middle:

``````public static Optional<String> findMiddleElementFromHead1PassIteratively(Node head) {
return Optional.empty();
}

while (fastPointer.hasNext() && fastPointer.next().hasNext()) {
fastPointer = fastPointer.next().next();
slowPointer = slowPointer.next();
}

return Optional.ofNullable(slowPointer.data());
}``````

We can test this solution with a simple unit test using lists with both odd and even number of elements:

``````@Test

assertEquals("3", MiddleElementLookup
createNodesList(5)).get());
assertEquals("2", MiddleElementLookup
reateNodesList(4)).get());
}``````

### 3.3. Finding the Middle Element in One Pass Recursively

Another way to solve this problem in one pass is by using recursion. We can iterate till the end of the list to know the size and, in the callbacks, we just count until the half of the size.

To do this in Java, we're going to create an auxiliary class to keep the references of the list size and the middle element during the execution of all the recursive calls:

``````private static class MiddleAuxRecursion {
Node middle;
int length = 0;
}``````

Now, let's implement the recursive method:

``````private static void findMiddleRecursively(
Node node, MiddleAuxRecursion middleAux) {
if (node == null) {
// reached the end
middleAux.length = middleAux.length / 2;
return;
}
middleAux.length++;
findMiddleRecursively(node.next(), middleAux);

if (middleAux.length == 0) {
// found the middle
middleAux.middle = node;
}

middleAux.length--;
}``````

And finally, let's create a method that calls the recursive one:

``````public static Optional<String> findMiddleElementFromHead1PassRecursively(Node head) {

return Optional.empty();
}

MiddleAuxRecursion middleAux = new MiddleAuxRecursion();
return Optional.of(middleAux.middle.data());
}``````

Again, we can test it in the same way as we did before:

``````@Test
assertEquals("3", MiddleElementLookup
createNodesList(5)).get());
assertEquals("2", MiddleElementLookup
createNodesList(4)).get());
}``````

## 4. Conclusion

In this article, we've introduced the problem of finding the middle element of a linked list in Java, and we've shown different ways of solving it.

We've started from the simplest approach where we kept track of the size, and after that, we've continued with the solutions to find the middle element from the head node of the list.

As always, the full source code of the examples is available over on GitHub.

### Get started with Spring 5 and Spring Boot 2, through the Learn Spring course:

>> CHECK OUT THE COURSE