跳转至

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

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

题目

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

示例： 

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

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

思路

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

为什么偶数取的是第二个：slow 最终停在 ⌊n/2⌋（0 索引）。循环条件是「fast 还能走满 2 步」，所以循环轮数 = 能凑成完整两两配对的次数 = ⌊n/2⌋，slow 就走 ⌊n/2⌋ 步：

n（索引 0..n-1） 循环轮数 slow 位置 含义
5（奇） 2 索引 2 正中间
6（偶） 3 索引 3 第二个中间（第一个是索引 2）

直观记忆：每轮 fast 吃掉 2 个节点，最后不足 2 个就停，所以 slow 走的是「下取整的一半」，天然落在偏后的那个中间。

两个循环条件分工不同（缺一即 NPE）：

  • fast != null 管偶数：fast 恰好走满 n 步变成 null，此时要停（否则访问 null.next）。
  • fast.next != null 管奇数：fast 停在最后一个节点，再走两步会越过 null，靠它拦住（否则执行 fast.next.next）。
  • 顺序不能换：先判 fast != null 才能安全访问 fast.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.next != null && fast.next.next != null——fast 提前一步停，slow 只走 ⌊(n-1)/2⌋ 步，偶数 n 时停在索引 n/2 - 1（第一个中间）。也可把 fast 的起点从 head 变成 head.next（参考 148. 排序链表 找中点断链的写法）。
  • 快慢指针是链表题的基础工具，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 步定位到中点，这是两次遍历，效率不如快慢指针法。

关联题