题目
给你单链表的头结点 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
解法
思路一：
既然是找中间结点，那么只需要使用“遍历+除2”来解决这个问题，但是也有需要注意的点：也就是 如果元素个数为奇数，则返回中间结点；为偶数，返回第二个中间结点。
class Solution { public: ListNode* middleNode(ListNode* head) { int n = 0; ListNode* cur = head; while (cur != nullptr) { ++n; cur = cur->next; } int k = 0; cur = head; while (k < n / 2) { ++k; cur = cur->next; } return cur; } };
思路二：
但是我们知道，假设有个中间数n，那么2n得到的就是最后一个数，既然这样我们是否可以使用两个速度不同的指针来实现这道题呢？使第二个指针的移动速度是第一个指针的两倍，那么等第二个指针走到最后的时候，第一个指针也就走到中间了。
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* middleNode(struct ListNode* head) { ListNode* midp; // 第二个思路：快慢双指针法 // slow和fast指针都指向头结点 // slow走一步，fast走两步 ListNode *slow, *fast; slow = fast = head; // 下述条件必须都满足才能进入循环,并且注意条件的顺序不能改（按照顺序来判断条件，那么反过来会形成短路） while (fast && fast->next) { slow = slow->next; //注意元素个数为奇数，则返回中间结点；为偶数，返回第二个中间结点 fast = fast->next->next; } return slow; }
