【Java 数据结构】链表的中间结点

 🔥博客主页🔥：【 坊钰_CSDN博客 】

欢迎各位点赞👍评论✍收藏⭐

题目出处：876. 链表的中间结点 - 力扣（LeetCode）

1. 题目

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

2. 解析

2.1 普通方法

• 可以看到只需要头指针向后走整个链表的一半长度即可找到目标节点
• 

2.2 快慢节点方法

•  定义两个节点，快节点（fast），慢节点（slow），快节点一次运动两次，慢节点一次运动一次，当快节点到头后，慢节点就是中间节点
• 原理：路程一样，速度 2 倍，一个运动完，另一个在中间
• 

3. 代码实现

 3.1 普通方法

class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null) return null;
        ListNode ret = head;
        int count = 0;
        while (ret != null) {
            count++;
            ret = ret.next;
        }
        count /= 2;
        ret = head;
        while (count != 0) {
            ret = ret.next;
            count--;
        }
        return ret;
    }
}

 3.2 快慢节点方法

class Solution {
    public ListNode middleNode(ListNode head) {
        if (head == null) return null;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null || fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

4. 小结

以上就是对该题的了解，具体还需宝子们去实践，如果觉得该博客对你有用的话，希望一键三连，点个关注不迷路，谢谢支持