Leetcode 876.链表的中间结点【C++】

地址：https://leetcode-cn.com/problems/middle-of-the-linked-list/

题目

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。

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

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

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

解题思路

思路很简单，定义两个指针并且都初始化为指向头结点，然后 cur 指针遍历整个链表，cur 每移动两个结点，mid 指针就往后移动一个结点，这样 mid 就始终是从 head 到 cur 的中间结点，直到 cur 遍历完整个链表，则 mid 所指向的结点即整个链表的中间结点。

需要注意头结点本就是中间结点，往后移动一个结点的时候，就应该将 mid 指向第二个结点。

👉🏻更好一点的办法是用 step 记录节点数，偶数个结点的时候 mid 就往后移动一个结点，这样就不用对头结点特殊处理。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* mid = head;//始终指向中间结点
        ListNode* cur = head;//当前结点
        int step = 1;//cur每隔一步往后移一位
        while (cur != NULL) {
            if (step == 0) {
                mid = mid->next;
                step = 1;
                cur = cur->next;
                continue;
            }
            cur = cur->next;
            step--;
        }
        return mid;
    }
};

更好一点的办法

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* mid = head;//始终指向中间结点
        ListNode* cur = head;//当前结点
        int step = 1;//结点数为偶数的时候指针mid往后移一位
        while (cur != NULL) {
            if (step % 2 == 0)
                mid = mid->next;
            cur = cur->next;
            step++;
        }
        return mid;
    }
};