题目描述
给你单链表的头结点 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
解题思路
这道题要求找到链表的中间节点,关键在于如何在一次遍历中找到中间位置。最优雅的解决方案是使用快慢指针(也称为'龟兔赛跑'算法)。
快慢指针原理
- 慢指针:每次移动一步
- 快指针:每次移动两步
当快指针到达链表末尾时,慢指针正好位于链表的中间位置。
特殊情况处理
- 链表长度为奇数:慢指针正好在中间节点
- 链表长度为偶数:慢指针在第二个中间节点(符合题目要求)
代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* fast = head; // 快指针,每次移动两步
struct ListNode* slow = head; // 慢指针,每次移动一步
while(fast && fast->next) {
slow = slow->next; // 慢指针移动一步
fast = fast->next->next; // 快指针移动两步
}
return slow; // 返回中间节点
}
代码详解
核心逻辑
while(fast && fast->next) {
slow = slow->next; // 慢指针前进一步
fast = fast->next->next; // 快指针前进两步
}
循环条件分析:
fast:确保快指针本身不为空fast->next:确保快指针可以安全地移动两步


