15、链表的中间节点：快慢指针法、计数法

链表的中间节点，这题我面试过不少人，自己也写过不下几十遍。说白了，就是给你一条单链表，让你找到正中间那个节点。如果节点总数是偶数，返回第二个中间节点——这是 LeetCode 上的标准定义。

嗯，咱们今天就把两种主流解法掰开揉碎讲清楚：快慢指针法和计数法。这两种思路，我在实际项目中都用过，各有各的适用场景。

15.1 问题定义

先明确一下输入输出：

• 输入：单链表的头指针 head
• 输出：中间节点的指针
• 约束：链表长度未知，只能单向遍历

举个例子：

1 → 2 → 3 → 4 → 5      // 奇数个节点，中间是 3
1 → 2 → 3 → 4 → 5 → 6  // 偶数个节点，中间是 4（第二个中间节点）

为什么会要求偶数时返回第二个？这是 LeetCode 的惯例，咱们就按这个来。如果你面试时遇到，最好跟面试官确认一下。

15.2 方法一：计数法（直观但低效）

计数法的思路很简单：先遍历一遍，数出链表总长度 n；再遍历第二遍，走到 n/2 的位置停下。

我刚开始学链表时，用的就是这招。虽然它要遍历两遍，但胜在逻辑清晰，不容易写错。

struct ListNode* middleNode_count(struct ListNode* head) {
    int count = 0;
    struct ListNode* cur = head;
    
    // 第一遍：数节点个数
    while (cur != NULL) {
        count++;
        cur = cur->next;
    }
    
    // 第二遍：走到中间位置
    int mid = count / 2;
    cur = head;
    for (int i = 0; i < mid; i++) {
        cur = cur->next;
    }
    
    return cur;
}

注意看，这里 mid = count / 2。如果 count = 5，mid = 2，走两步到 3（索引从0开始）。如果 count = 6，mid = 3，走三步到 4。完美符合「偶数时返回第二个中间节点」的要求。

15.3 方法二：快慢指针法（优雅且高效）

快慢指针法，这才是面试官想看到的解法。思路是这样的：

• 两个指针，slow 每次走一步，fast 每次走两步
• 当 fast 走到末尾时，slow 正好在中间

你想想看，这就像两个人跑步，一个速度是另一个的两倍。当快的跑完全程，慢的刚好跑了一半。

struct ListNode* middleNode_fastSlow(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;      // 慢指针走一步
        fast = fast->next->next; // 快指针走两步
    }
    
    return slow;
}

这里有个细节要注意：while 条件里为什么要同时判断 fast 和 fast->next？

因为如果链表节点数是奇数，fast 会停在最后一个节点（fast->next == NULL）。如果节点数是偶数，fast 会停在 NULL。两种情况下，循环都能正确退出。

15.4 两种方法对比

对比维度	计数法	快慢指针法
遍历次数	2次	1次
代码复杂度	低	中
额外信息	可同时获得链表长度	无
面试偏好	一般	推荐
适用场景	需要长度信息时	纯找中间节点

我个人习惯，如果只是单纯找中间节点，肯定用快慢指针。但如果后续逻辑还需要链表长度，计数法反而更省事——毕竟长度已经算出来了，不用再遍历一次。

15.5 核心逻辑流程图

下面这张图展示了快慢指针法的执行过程，我画的是奇数个节点的情况：

从图中可以清楚看到：slow 最终停在节点 3，这就是我们要找的中间节点。fast 走了两步后到达 NULL，循环结束。

15.6 实际项目中的选择

我在嵌入式项目中，经常用快慢指针法来做链表的分割操作。比如一个任务队列，我想把它均匀分成两半，让两个处理器核分别处理。这时候找到中间节点，然后断开链表，就完成了分割。

但有一次，我需要同时知道队列的总长度来做负载均衡。这时候我就用了计数法——反正都要算长度，多遍历一次也无所谓。

所以我的建议是：

• 面试时：优先写快慢指针法，面试官会眼前一亮
• 实际项目中：根据需求选，不要为了炫技而炫技

好了，链表的中间节点就讲到这里。两种方法，一个直观一个优雅，你掌握了吗？