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

一、思路

这里分为链表结点个数是 奇数 和 偶数 两种情况。

如果是奇数，中间结点只有一个，返回即可；如果是偶数，中间结点则有两个，这里要求返回第二个。


上述图片展示的就是奇数的情况，此时中间结点就是 34。


以上展示的就是偶数的情况，此时看到中间结点是 23 和 34 两个，但是我们返回的是第二个，
因此此时实际返回的是 34 这个结点。

定义一个 slow 和 fast 变量来表示快慢指针，slow 每次走一步，代表慢指针；fast 每次走两步，代表快指针。


二、步骤

1、定义 slow 和 fast ，然后将它们都指向头结点，从头结点开始向后移动。


接下来就是让 slow 和 fast 按照各自的步数移动。


2、写一个循环来找中间的结点。

我们怎么来找中间结点呢?

因为 fast 每次要比 slow 多走一步，因此 fast 一定会比 slow 走得多，当然这里是分为奇数和偶数两种情况的。

如果结点个数是奇数，当 fast 的下一个结点 为 null 的时候，此时当前 slow 指向的位置就是中间结点，返回中间结点即返回 slow。

根据上述图片可以看到，当 fast 的下一个结点为空的时候 slow 确实是指向了中间结点。

如果结点个数是偶数，当 fast 指向的结点 为 null 的时候，此时循环就遍历结束了，并且当前 slow 指向的位置就是第二个中间结点，返回中间结点即返回 slow。

可以看到当前 fast 指向空的时候，此时 slow 指向的就是第二个中间结点。

三、代码

首先是要创建两个指针来指向链表的头结点。

ListNode fast = this.head;
ListNode slow = this.head;

我们知道分为奇数和偶数两种情况后，而 fast == null 与 fast.next == null 分别代表上述两种情况。

循环的判断条件就是 fast == null && fast.next == null ，也就是说，当不满足上述条件后，slow 此时就指向了中间结点，此时一定跳出循环，然后返回 slow 结点即可。

while (fast != null && fast.next != null) {
   
}
   return slow;//此时的slow就是中间的结点

因为 slow 是慢指针，一次只会走一步，要让 slow 指向它的下一个结点就使用以下代码。

 slow = slow.next;//走一个

代码是让 slow 指向它的下一个结点。


fast 是快指针，一次走两步使用以下代码。

 fast = fast.next.next;//走两个

代码是让 fast 指向它的下一个结点的下一个结点。

完整代码展示

//2.返回中间的结点
public ListNode middleNode() {
    //1.定义一个fast和slow
    ListNode fast = this.head;
    ListNode slow = this.head;

    //2.fast每次走两步，slow每次走一步
    //判断奇数和偶数个结点
    while (fast != null && fast.next != null) {
        //如果是偶数就返回第二个中间结点
        //如果是奇数就返回中间的结点
        fast = fast.next.next;//走两个
        slow = slow.next;//走一个
    }
    return slow;//此时的slow就是中间的结点
} 

可以看到当前的代码通过了牛客上的测试。