876. 链表的中间结点（Middle of the Linked List）

频次 ★★ · 难度 🟢 · 高频：美团

题目

给定链表头节点，返回链表的中间节点；如果有两个中间节点，返回第二个。

示例：

输入: 1 -> 2 -> 3 -> 4 -> 5
输出: 节点 3

输入: 1 -> 2 -> 3 -> 4 -> 5 -> 6
输出: 节点 4（第二个中间节点）

思路

快慢指针：慢指针每次走一步，快指针每次走两步。快指针到达末尾时，慢指针正好在中点。链表长度为偶数时，快指针会先变成 null（走到最后一个节点的 next），此时慢指针停在第二个中间节点，天然满足题目要求，不用额外判断奇偶。

代码

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

复杂度

• 时间：O(n) — 一次遍历
• 空间：O(1)

边界条件

• 只有一个节点：循环不执行，直接返回 head 本身。
• 两个节点：fast.next 存在但 fast.next.next 为 null，循环执行一次后 fast 停在第二个节点，slow 停在第二个节点——正好是”两个中间节点中的第二个”，符合题目要求。

变式

• 要求返回第一个中间节点（长度为偶数时）：把 fast 的起点从 head 变成 head.next（参考 148. 排序链表 找中点断链的写法），或者把循环条件改成 fast.next != null && fast.next.next != null。
• 快慢指针是链表题的基础工具，141. 环形链表、142. 环形链表 II、148. 排序链表 找中点都是同一套模板。

易错点

• 循环条件 fast != null && fast.next != null 中两个判断都不能少，顺序也不能换（必须先判断 fast != null 再访问 fast.next），否则链表长度为偶数时会访问空指针。
• 容易和”找倒数第 k 个节点”（19 题）的双指针搞混：本题两个指针都从 head 出发、速度不同；19 题两个指针速度相同、但起点错开 n 步，是两种不同的”快慢指针”用法。

面试追问

• 为什么”快指针走两步、慢指针走一步”能找到中点？ 快指针的路程始终是慢指针的两倍，当快指针走完全程（n 步）时，慢指针恰好走了 n/2 步，也就是中点位置；这是”倍速指针定位比例位置”的通用技巧，只要能保证两个指针的速度比是 2:1，就能定位到中点。
• 不遍历两次（先算长度再定位）、只用一次遍历还有别的方法吗？ 快慢指针本身就是”只需一次遍历”的方法；如果不用双指针，只能先遍历一次算出总长度 n，再遍历 n/2 步定位到中点，这是两次遍历，效率不如快慢指针法。

关联题

• 同套路：141. 环形链表I、142. 环形链表II —— 快慢指针族
• 进阶：234. 回文链表 —— 找中点 + 反转后半段的组合应用；148. 排序链表 —— 归并切分靠本题找中点
• 易混：19. 删除倒数第N个结点 —— 同为双指针定位，但用固定间距不是速度差