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(
LinkedList<String> linkedList) {
if (linkedList == null || linkedList.isEmpty()) {
return Optional.empty();
}
return Optional.of(linkedList.get(
(linkedList.size() - 1) / 2));
}
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) {
Node head = new Node("1");
Node current = head;
for (int i = 2; i <= n; i++) {
Node newNode = new Node(String.valueOf(i));
current.setNext(newNode);
current = newNode;
}
return head;
}
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) {
if (head == null) {
return Optional.empty();
}
// calculate the size of the list
Node current = head;
int size = 1;
while (current.hasNext()) {
current = current.next();
size++;
}
// iterate till the middle element
current = head;
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) {
if (head == null) {
return Optional.empty();
}
Node slowPointer = head;
Node fastPointer = head;
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
void whenFindingMiddleFromHead1PassIteratively_thenMiddleFound() {
assertEquals("3", MiddleElementLookup
.findMiddleElementFromHead1PassIteratively(
createNodesList(5)).get());
assertEquals("2", MiddleElementLookup
.findMiddleElementFromHead1PassIteratively(
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) {
if (head == null) {
return Optional.empty();
}
MiddleAuxRecursion middleAux = new MiddleAuxRecursion();
findMiddleRecursively(head, middleAux);
return Optional.of(middleAux.middle.data());
}
Again, we can test it in the same way as we did before:
@Test
void whenFindingMiddleFromHead1PassRecursively_thenMiddleFound() {
assertEquals("3", MiddleElementLookup
.findMiddleElementFromHead1PassRecursively(
createNodesList(5)).get());
assertEquals("2", MiddleElementLookup
.findMiddleElementFromHead1PassRecursively(
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.