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

曾经终败给现在 2023-10-13 10:52 5阅读 0赞

**一、思路**  
  
这里分为链表结点个数是 **奇数** 和 **偶数** 两种情况。

如果是奇数，中间结点只有一个，返回即可；如果是偶数，中间结点则有两个，这里要求返回第二个。  
  
![9e45896f7bca4d03bbcbb309bb5ebccc.png_pic_center][]  
上述图片展示的就是奇数的情况，此时中间结点就是 34。  
  
![7b780c81d2bd42939528299f9741180d.png_pic_center][]  
以上展示的就是偶数的情况，此时看到中间结点是 23 和 34 两个，但是我们返回的是第二个，  
因此此时实际返回的是 34 这个结点。

定义一个 slow 和 fast 变量来表示快慢指针，slow 每次走一步，代表慢指针；fast 每次走两步，代表快指针。  
  
  
**二、步骤**  
  
1、**定义 slow 和 fast ，然后将它们都指向头结点，从头结点开始向后移动。**  
  
![ab0762e4b6f64ea88b0ac3f3bd667445.png_pic_center][]  
接下来就是让 slow 和 fast 按照各自的步数移动。  
  
  
2、**写一个循环来找中间的结点。**  
  
我们怎么来找中间结点呢?

因为 fast 每次要比 slow 多走一步，因此 fast 一定会比 slow 走得多，当然这里是分为奇数和偶数两种情况的。  
  
如果结点个数是奇数，当 fast 的下一个结点 为 null 的时候，此时当前 slow 指向的位置就是中间结点，返回中间结点即返回 slow。

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

如果结点个数是偶数，当 fast 指向的结点 为 null 的时候，此时循环就遍历结束了，并且当前 slow 指向的位置就是第二个中间结点，返回中间结点即返回 slow。  
![c67eec68025948ba81fc8a570c8a14ab.png_pic_center][]  
可以看到当前 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就是中间的结点
    }

![8d8700d208384a72aed25839176e7433.png_pic_center][]  
可以看到当前的代码通过了牛客上的测试。

[9e45896f7bca4d03bbcbb309bb5ebccc.png_pic_center]: https://img-blog.csdnimg.cn/9e45896f7bca4d03bbcbb309bb5ebccc.png#pic_center
[7b780c81d2bd42939528299f9741180d.png_pic_center]: https://img-blog.csdnimg.cn/7b780c81d2bd42939528299f9741180d.png#pic_center
[ab0762e4b6f64ea88b0ac3f3bd667445.png_pic_center]: https://img-blog.csdnimg.cn/ab0762e4b6f64ea88b0ac3f3bd667445.png#pic_center
[162b3c2985fa4ef68e1a63e0caa78da4.png_pic_center]: https://img-blog.csdnimg.cn/162b3c2985fa4ef68e1a63e0caa78da4.png#pic_center
[c67eec68025948ba81fc8a570c8a14ab.png_pic_center]: https://img-blog.csdnimg.cn/c67eec68025948ba81fc8a570c8a14ab.png#pic_center
[8d8700d208384a72aed25839176e7433.png_pic_center]: https://img-blog.csdnimg.cn/8d8700d208384a72aed25839176e7433.png#pic_center