**I just announced the new ***Spring 5* modules in REST With Spring:

*Spring 5*modules in REST With Spring:

**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 public 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 public 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.

## Leave a Reply