在Java中查找链表的中间元素

1. 概述

本文将深入探讨如何在 Java 中高效地查找链表的中间元素。

我们会先分析常见场景和难点，然后逐一介绍几种实用的解决方案，包括踩坑点和优化思路。对于有经验的开发者来说，这属于基础但高频的面试与实际问题，掌握多种解法能让你在不同场景下游刃有余。

2. 维护链表大小信息

最简单粗暴的方式是：在插入元素时就维护链表的 size。一旦我们知道总长度，中间位置自然就明确了——直接计算索引即可，问题瞬间降维。

以 Java 自带的 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));
}

⚠️ 但要注意：LinkedList.get(index) 并不是 O(1) 操作！它内部仍需遍历节点。我们来看 JDK 源码中的 node(index) 方法：

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;
    }
}

✅ 优点：逻辑清晰，代码简洁
❌ 缺点：频繁随机访问时性能差，尤其在单向链表中无法利用双向指针优化

所以这种“取巧”方式仅适用于你能控制数据结构设计的场景。如果只能从 head 开始遍历？那就得看下面的硬核解法了。

3. 仅知道头节点时查找中间元素

更常见的现实是：你只拿到一个 head 节点，链表长度未知。这时候就不能依赖 size 了，必须通过遍历来解决。

我们先定义一个简单的单向链表节点类：

public static class Node {

    private Node next;
    private String data;

    public Node(String data) {
        this.data = data;
    }

    public Node next() {
        return next;
    }

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

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

    public String data() {
        return data;
    }

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

为了方便测试，我们写个辅助方法生成指定长度的链表：

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;
}

比如 createNodesList(5) 会生成：1 → 2 → 3 → 4 → 5

3.1. 先遍历求长度，再找中间节点

最直观的思路：

第一次遍历：统计总长度 size
第二次遍历：从头走 (size - 1)/2 步，即为中间节点

实现如下：

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

    // 第一次遍历：计算长度
    Node current = head;
    int size = 1;
    while (current.hasNext()) {
        current = current.next();
        size++;
    }

    // 第二次遍历：走到中间
    current = head;
    for (int i = 0; i < (size - 1) / 2; i++) {
        current = current.next();
    }

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

✅ 实现简单，容易理解
❌ 时间复杂度 O(n)，但需要两次遍历 —— 性能不够优雅

面试中如果你只答出这一种，基本会被要求优化。

3.2. 一次遍历：快慢指针（推荐）

这才是真正“高级感”拉满的解法——快慢指针（Slow-Fast Pointer）技巧。

核心思想：

定义两个指针：slow 和 fast
fast 每次走 2 步，slow 每次走 1 步
当 fast 到达末尾时，slow 正好在中间

🎯 图解过程（以 5 个节点为例）：

初始：
slow → 1
fast → 1

第1轮：
       slow → 2
              fast → 3

第2轮：
            slow → 3
                     fast → 5 (next=null，停止)

此时 slow 指向 3，正是中间元素

代码实现：

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

    Node slowPointer = head;
    Node fastPointer = head;

    // 条件：fast 还能再走两步
    while (fastPointer.hasNext() && fastPointer.next().hasNext()) {
        fastPointer = fastPointer.next().next();
        slowPointer = slowPointer.next();
    }

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

✅ 仅需一次遍历，O(n) 时间，O(1) 空间
✅ 面试高频考点，必须掌握
⚠️ 注意边界判断：空链表、单节点、偶数长度

测试用例验证奇偶情况：

@Test
void whenFindingMiddleFromHead1PassIteratively_thenMiddleFound() {
    assertEquals("3", MiddleElementLookup
      .findMiddleElementFromHead1PassIteratively(createNodesList(5)).get());
    assertEquals("2", MiddleElementLookup
      .findMiddleElementFromHead1PassIteratively(createNodesList(4)).get());
}

对于偶数长度（如 4），返回第 2 个元素（即前半部分的尾部），符合 (n-1)/2 的下取整逻辑。

3.3. 一次遍历：递归解法（拓展思路）

除了迭代，也可以用递归实现“一次遍历”。关键在于利用递归的回溯过程来计数。

思路：

一路递归到底（类似 DFS）
回溯时开始计数，当计数到达 size/2 时，当前节点就是中间节点

由于 Java 没有指针引用传递，我们需要一个辅助类来保存状态：

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

递归主体逻辑：

private static void findMiddleRecursively(Node node, MiddleAuxRecursion middleAux) {
    if (node == null) {
        // 到达尾部，开始回溯，此时 length 是总长度
        middleAux.length = middleAux.length / 2;
        return;
    }
    
    middleAux.length++;  // 向下递归时累加长度
    findMiddleRecursively(node.next(), middleAux);

    // 回溯阶段：length 表示“距离尾部还有多少步”
    if (middleAux.length == 0) {
        middleAux.middle = node; // 正好是中间节点
    }
    
    middleAux.length--; // 回溯时递减
}

封装调用入口：

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());
}

测试验证：

@Test
void whenFindingMiddleFromHead1PassRecursively_thenMiddleFound() {
    assertEquals("3", MiddleElementLookup
      .findMiddleElementFromHead1PassRecursively(createNodesList(5)).get());
    assertEquals("2", MiddleElementLookup
      .findMiddleElementFromHead1PassRecursively(createNodesList(4)).get());
}

✅ 思路巧妙，体现递归对称美
❌ 使用了额外的栈空间，链表过长可能栈溢出
💡 适合展示算法思维，生产环境建议用快慢指针

4. 总结

方法	时间复杂度	空间复杂度	是否推荐
维护 size	O(1) 取值	O(1)	✅ 特定场景可用
两次遍历	O(n)	O(1)	⚠️ 可行但不优雅
快慢指针（迭代）	O(n)	O(1)	✅✅✅ 强烈推荐
递归回溯	O(n)	O(n) 栈空间	✅ 拓展思路

📌 核心结论：

日常开发中，优先使用 快慢指针 解法，简单高效无副作用
面试中如果被问到，先说两次遍历，再主动优化到快慢指针，展现思维过程
递归解法虽酷，但要考虑栈安全，别为了炫技埋雷

所有示例代码已托管至 GitHub：https://github.com/baeldung/java-algorithms

Persistence

REST

Security