algorithm-base 链表篇：面试题 02.03 链表中间节点——快慢指针一次遍历定位链表中心

• 文档
• 教程
• 知识库

导读

在算法刷题与面试中，链表是最基础也最高频的考点之一。本文以 algorithm-base 仓库中 面试题 02.03. 链表中间节点 为主体，深入讲解如何用快慢指针（Floyd 龟兔赛跑思想）在一次遍历、O(1) 额外空间内找到单链表的中间节点，并与仓库中倒数第 k 个节点、环形链表、回文链表 等经典题目串成一条"链表双指针"知识线。读完本文，你将掌握快慢指针的推导思路、奇偶长度边界处理，以及中间节点在后续复杂题目中的复用价值。

一、题目描述

给定一个头结点为head的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5] 输出：节点 3

说明：因为只有一个中间节点。

示例 2：

输入：[1,2,3,4,5,6] 输出：节点 4

说明：有两个中间节点所以返回后面那个。

该题对应力扣 876. 链表的中间结点，同时也是《程序员面试金典》面试题 02.03，可见其经典程度。

前提约束：链表非空，因此无需处理head == null的空链表边界；但链表长度可为奇数或偶数，这直接影响循环条件的设计，下文会重点分析。

二、由浅入深的三种思路推演

拿到题目后，先不急着看题解，可以按下面三个阶段自我推演：

1. 两次遍历法（最容易想到）

第一次遍历链表，统计节点总数n；第二次遍历，走到第n / 2 + 1个节点（注意是第二个中间节点，所以取n/2的下一个）即为答案。

• 时间复杂度：O(n)，空间复杂度：O(1)。
• 缺点：需要两次遍历，链表越长代价越明显。

2. 数组辅助法（空间换时间）

利用数组将所有链表元素先存入，再直接通过索引取得中间节点：

ListNode[] arr = ...; // 顺序存储所有节点 return arr[arr.length / 2];

• 时间复杂度：O(n)，空间复杂度：O(n)。
• 缺点：需要额外辅助空间，在"只允许常数级额外空间"的约束下不满足要求。

3. 快慢指针法（一次遍历，零辅助空间）

这正是本文的主角。上面的思路推演在仓库原文中也有完整铺垫（见 面试题 02.03. 链表中间节点）。

三、快慢指针核心思想与动画解读

1. 思路来源：与"倒数第 k 个节点"的联系

在仓库的剑指 offer 22 链表中倒数第 k 个节点 中，我们使用一前一后双指针：两个指针之间始终相差k - 1位，当前指针到达链表尾部时，后指针恰好指向倒数第 k 个节点。

中间节点问题可以看作这个思想的一个变体：我们不需要两个指针保持固定间距，而是让一个指针走得快、一个指针走得慢——这种"快慢"双指针正是链表题目的高频套路，被称作快慢指针（fast-slow pointer）。

2. 算法过程

• 快指针fast每次走两步（fast = fast.next.next）；
• 慢指针slow每次走一步（slow = slow.next）；
• 当快指针到达链表尾部时，慢指针恰好位于链表中间。

3. 奇偶长度的两种情形

链表中节点个数可能为奇数也可能为偶数，这是本题最核心的边界：

关键点：两种情况下我们输出的都是slow指针指向的节点，即"两个中间节点的第二个"。

为什么会这样？因为循环条件写成while (fast != null && fast.next != null)：

• 奇数长度：fast最终停在最后一个节点（fast.next == null），此时slow移动了(n-1)/2步，正好落在中间；
• 偶数长度：fast最终越界为null，此时slow移动了n/2步，落在第n/2 + 1个节点，也就是第二个中间节点。

这一"取第二个中间节点"的约定与力扣题目要求完全一致。仓库原文配有一张 CSDN 上的动画模拟图（20210321131249789.gif），形象地展示了快慢指针的推进过程，建议读者结合动画自行在纸上推演一遍。

四、题目代码（六种语言实现）

仓库原文给出了 Java、C++、JS、Python、Swift、Go 六种语言的完整实现，全部保持同一套循环条件逻辑，可直接复制运行：

Java

class Solution { public ListNode middleNode(ListNode head) { ListNode fast = head;//快指针 ListNode slow = head;//慢指针 //循环条件，思考一下跳出循环的情况 while (fast!=null && fast.next != null) { fast = fast.next.next; slow = slow.next; } //返回slow指针指向的节点 return slow; } }

C++

class Solution { public: ListNode* middleNode(ListNode* head) { ListNode * fast = head;//快指针 ListNode * slow = head;//慢指针 //循环条件，思考一下跳出循环的情况 while (fast != nullptr && fast->next != nullptr) { fast = fast->next->next; slow = slow->next; } //返回slow指针指向的节点 return slow; } };

JavaScript

var middleNode = function (head) { let fast = head; //快指针 let slow = head; //慢指针 //循环条件，思考一下跳出循环的情况 while (fast && fast.next) { fast = fast.next.next; slow = slow.next; } //返回slow指针指向的节点 return slow; };

Python

class Solution: def middleNode(self, head: ListNode) -> ListNode: fast = head # 快指针 slow = head # 慢指针 # 循环条件，思考一下跳出循环的情况 while fast is not None and fast.next is not None: fast = fast.next.next slow = slow.next # 返回slow指针指向的节点 return slow

Swift

class Solution { func middleNode(_ head: ListNode?) -> ListNode? { var fast = head //快指针 var slow = head //慢指针 //循环条件，思考一下跳出循环的情况 while fast != nil && fast?.next != nil { fast = fast?.next?.next slow = slow?.next } //返回slow指针指向的节点 return slow } }

Go

func middleNode(head *ListNode) *ListNode { // 快慢指针 fast, slow := head, head for fast != nil && fast.Next != nil { fast = fast.Next.Next slow = slow.Next } return slow }

复杂度分析

• 时间复杂度：O(n)，快慢指针各遍历链表一次（整体只扫描一遍，快指针步长 2，总步数约为 n/2）；
• 空间复杂度：O(1)，仅使用两个指针变量，未开辟任何辅助容器。

五、快慢指针知识线与仓库源码佐证

1. ListNode 节点的定义约定

仓库在 Leetcode常用类和函数.md 中给出了刷题常用的ListNode初始化写法：

ListNode list = new ListNode(0);

即每个链表节点持有val与next引用，构成链式结构。上面六种语言的middleNode均以该结构为前提。

2. 同类题一：链表中倒数第 k 个节点（固定间距双指针）

在 剑指offer22倒数第k个节点.md 中，算法思想是：一个指针先移动k-1位，然后两个指针同速移动、始终保持相差 k-1 位，当前指针到达链表尾部时，后指针指向倒数第 k 个节点。

对比可知：

两者都是"用指针位移关系定位链表位置"的经典应用，建议放在一起对比学习。

3. 同类题二：环形链表（快慢指针追及）

在 leetcode141环形链表.md 中，同样使用快慢指针：快指针一次走两步、慢指针一次走一步，若链表有环，快指针若干圈后必然追上慢指针（fast == slow即为有环证据）。

while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) return true; }

可以看到循环条件与本题完全一致——这说明"快指针每次跳两步 + 判空保护"是快慢指针在单链表上的通用骨架，理解本题后即可无缝迁移到环形检测场景。

4. 进阶应用：回文链表（中间节点的实战价值）

中间节点最大的实战价值体现在复合题目中。234. 回文链表.md 给出了一个非常典型的组合套路：

1. 先找到中间节点（searchmidnode）；
2. 翻转后半段链表（reverse）；
3. 双指针遍历前后两半比较值，判断是否为回文；
4. 结束后再翻转一次，还原链表原始结构。

值得注意的是，回文链表中需要的是第一个中间节点，因此其查找函数用了不同的循环条件：

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

对比本题的while (fast != null && fast.next != null)，仅一处条件不同，返回的中间节点就从"第二个"变成了"第一个"。这恰好印证了仓库原文的提示："如果有两个中间节点返回第一个，昨天的题目是第二个"。两篇文档对照阅读，可以彻底吃透中间节点两种取法背后的循环条件差异。

六、易错点与面试延伸

1. 循环条件为什么必须判fast != null && fast.next != null

• 若只判fast != null：偶数长度时fast会在倒数第二个节点先走fast.next.next得到null，下一次循环再访问fast.next会触发空指针异常；
• 若只判fast.next != null：当fast已为null时访问fast.next同样报错。

所以两个条件缺一不可，顺序上先判fast != null保证fast.next可安全访问，再判fast.next != null保证fast.next.next可安全访问。

2. "返回第二个中间节点"的含义

题目明确约定：偶数长度下返回两个中间节点的后一个。例如[1,2,3,4,5,6]返回节点 4。若题目改为返回第一个中间节点，只需把循环条件换成fast.next != null && fast.next.next != null（见上节回文链表写法）。

3. 面试加分项：不修改链表结构

在回文链表等复合题中，翻转后半段后务必再次翻转还原，以保持输入链表结构不被破坏（仓库原文在 234. 回文链表.md 中对此有明确注释："我们不可以破坏初始结构"）。中间节点定位本身不改动任何指针指向，天然安全。

七、总结

链表中间节点看似简单，却是快慢指针体系的"题眼"所在：

• 掌握一次遍历、O(1) 空间的快慢指针解法；
• 理解奇偶长度下循环条件与返回节点的关系；
• 能够将中间节点作为子步骤，复用到回文链表、链表重排（如 leetcode 143）、奇偶链表等进阶题目中。

建议结合仓库中 面试题 02.03. 链表中间节点 原文的动画，以及倒数第 k 个节点、环形链表、回文链表、反转链表 四篇姊妹篇，把"链表双指针"这一族题目一次性打通。

• 文档
• 教程
• 知识库