题目----力扣--链表的中间结点

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

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

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;
    }
};

/**
 * 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;
}