【Java】链表的中间结点

🎈目录🎈

问题描述🔒

解题分析🔑

 代码实现🔓

---

题目入口📌：链表的中间结点

问题描述

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

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

输入输出实例:

解题分析

        这道题我们需要找到单向链表的中间结点，普通做法我们可以先遍历一次链表，得到链表的长度，然后在寻找中间结点。

        但是如果作为面试题的话，我们就需要再上升一高度，在只遍历一次就找到中间结点。

如何在一次遍历中就找到中间结点呢？我们可以运用 路程 = 速度 x  时间 的思想，如下图，

当  ，那么在相同时间内，黄车跑的路程 肯定是 绿车跑路程的2倍。

       所以我们也可以设置两个指针在链表中，一个跑的快一个跑的慢，当快的跑到终点时，慢的恰好在中间位置，这种思路通常叫做快慢指针思想。

        现在我们知道具体该怎么操作之后，就需要确定什么条件下 快指针 停下，慢指针 正好指正中间结点。而链表中的结点个数分为偶数个和奇数个，所以我们的判断条件肯不止一个，这两种情况需要具体分析。

我们先来看奇数个结点，如下图，快指针（fast）一次走两步，而慢指针（slow）一次走一步,当 fast.next == null 时，slow 正好指向中间结点。

所以我们便确定了一个判断条件 fast.next == null。

 偶数个结点，对于偶数来说有两个中间结点，则返回第二个中间结点。其实我们可以稍微做一下转换。例如有一个链表长度为4，我们可以在该链表尾部虚拟一个 null  结点，如下图

 我们就可以把偶数个结点的链表看成奇数个结点的链表，只不过判断条件 变成fast == null。

所以我们便又确定了一个判断条件 fast == null。

 综上所述，我们的代码就可以写成如下形式

while(fast.next != null && fast != null){//这两个条件必须同时满足
    ....
}

        这里有个细节问题，如果我们写成 fast.next != null && fast != null  编译器可能会报出空指针异常。

         在偶数结点的链表中，fast最后为null。判断条件时 就会先执行 fast.next != null  而非 fast != null 所以就会出现 空指针异常的情况 ，我们所要做的就是把两个条件的位置换一下。

while(fast != null && fast.next != null){
    fast = fast.next.next;
    slow = slow.next;
}

 代码实现

class Solution {
    public ListNode middleNode(ListNode head) {
        if(head.next == null) return head;//当链表为null时，直接返回
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        
        return slow;
 
    }
}