算法：力扣876.链表的中间结点

「这是我参与11月更文挑战的第12天，活动详情查看：2021最后一次更文挑战」

题目描述

给定一个头结点为 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，我们返回第二个结点。

• 提示：

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

题目分析

根据题目，本题使用快慢指针的思想，快指针每次走两步，慢指针每次走一步，当快指针走完，则慢指针就刚好到中间位置，返回慢指针即可。

情况一: 如果为奇数个节点（若2n+1个）,则快指针需要执行 (2n+1-1)/2 = n次遍历完成，对于2n+1个节点来说，中间节点就是第n个，此时慢节点恰好前进n步，则直接返回慢指针指向的节点。

情况二: 如果为偶数个节点（若为2n个)，按照规律来看，快指针每次走两步，则会落在奇数点节点上，对于快指针我们假设需要走x步，结束，则 2n< 2x+1 <2(n+1) => n-1/2< x <n+1/2 若x为整数，则x取值n, 根据题目中描述，如果为偶数点个数时，取中间两个节点后一个节点，也就是 n+1对应的节点，所以慢指针取其后面一个下标数。

注意遍历链表时候的条件，不仅要fast不为空，并且fast.next也不为空。不然走到最后一个节点的时候，fast还往后访问就会抛错了。

时间复杂度：O(N)，其中N 是数组的长度。

空间复杂度：O(1)，只需要常数空间存放 slow 和 fast 两个指针。。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null) return null;
        ListNode fast = head, slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
复制代码

\