✨题目

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

✨样例

示例 1： 输入：[1,2,3,4,5] 输出：此列表中的结点 3 （序列化形式：[3,4,5]）

示例2： 输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 （序列化形式：[4,5,6]）

✨提示

• 给定链表的结点数介于 1 和 100 之间。

👍解题

方法一：利用数组

链表和数组相比来说，不好求中间节点的原因在于我们没办法直接按照 长度 / 2 的方式，来得到中间的节点，所以我们不妨遍历整个链表，然后把所有节点都添加到 vector 中。然后直接返回 vector[ vector.size( ) / 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) {
        vector<ListNode*> arr;
        while(head != NULL){
            arr.push_back(head); // 把所有的节点添加到vector中
            head = head->next;
        }
        int len = arr.size();
        return arr[len / 2];
    }
};

方法二：单指针

上面说到，链表和数组相比来说，不好求中间节点的原因在于我们没办法直接按照 **长度 / 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* node = head;
        int sum = 0;
        int temp = 0;
        while(node != NULL){
            sum ++;
            node = node->next;
        }
        while(temp < sum / 2){
            head = head->next;
            temp ++;
        }
        return head;
    }
};

方法三：快慢指针

不妨设置两个指针同时来遍历链表，其中一个快指针的步长为2，慢指针的步长为1，这样的话，当快指针遍历到末尾的时候，慢指针一定是在链表的中间。

/**
 * 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* high = head;
        ListNode* low = head;
        while(high != NULL && high->next != NULL){
            high = high->next->next;
            low = low->next;
        }
        return low;
    }
};