day133—快慢指针—链表的中间结点（LeetCode-876）

题目描述

给你单链表的头结点head，请你找出并返回链表的中间结点。

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

示例 1：

输入：head = [1,2,3,4,5]输出：[3,4,5]解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]输出：[4,5,6]解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

• 链表的结点数范围是[1, 100]
• 1 <= Node.val <= 100

解决方案：

这段代码的核心功能是找到单链表的中间节点（若链表节点数为偶数，返回第二个中间节点；奇数则返回正中间节点），采用「快慢指针（龟兔赛跑）」的经典方法实现，时间复杂度O(n)、空间复杂度O(1)，是找链表中间节点的最优解法。

核心逻辑

代码利用快慢指针的步长差异，让快指针走得更快，当快指针到达链表末尾时，慢指针恰好停在中间位置：

1. 指针初始化：慢指针low和快指针fast都从链表头节点head出发；
2. 快慢遍历：循环条件为fast不为空且fast->next不为空（保证快指针能走两步）：
   • 慢指针low每次走 1 步（low = low->next）；
   • 快指针fast每次走 2 步（fast = fast->next->next）；
3. 返回结果：循环结束时，快指针已走到链表末尾（或超出末尾），慢指针恰好指向链表的中间节点，直接返回low即可。

总结

1. 核心思路：快慢指针步长比 1:2，利用步长差让慢指针 “天然” 停在中间位置，无需统计链表长度；
2. 关键细节：循环条件fast && fast->next避免快指针访问空指针的next导致崩溃；
3. 结果特性：偶数节点返回第二个中间节点（如 1→2→3→4 返回 3），奇数节点返回正中间（如 1→2→3 返回 2），符合常规题目要求。

函数源码：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* middleNode(ListNode* head) { ListNode* low=head; ListNode* fast=head; while(fast && fast->next){ low=low->next; fast=fast->next->next; } return low; } };