1. Overview
1.概述
In this tutorial, we’re going to explain how to find the middle element of a linked list in Java.
在本教程中，我们将解释如何在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
2.保持跟踪尺寸
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:
让我们看一个使用LinkedList的Java实现的例子。
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:
如果我们检查LinkedList类的内部代码，我们可以看到在这个例子中，我们只是在遍历列表，直到到达中间的元素。
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
3.在不知道大小的情况下找到中间的位置
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:
让我们创建一个Node类，它存储String值。
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
3.1.首先找到尺寸
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
3.2.一次性迭代找到中间元素
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.
要做到这一点，我们需要两个指针同时在列表中迭代。一个指针将在每次迭代中推进2个节点，另一个指针每次迭代只推进一个节点。
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
3.3.递归地寻找中间元素
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:
为了在Java中做到这一点，我们要创建一个辅助类，在所有递归调用的执行过程中保持对列表大小和中间元素的引用。
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
4.结论
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.
在这篇文章中，我们介绍了在Java中寻找链表中间元素的问题，并展示了解决这个问题的不同方法。
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.
一如既往，这些示例的完整源代码可在GitHub上获得。