题解 | #牛牛队列成环#java

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return bool布尔型
     */
    public boolean hasCycle (ListNode head) {
        // write code here
// 如果链表为空或只有一个节点，那么肯定不存在环，直接返回 false
        if (head == null || head.next == null) {
            return false;
        }

        // 定义快指针和慢指针，初始时都指向链表的头节点
        ListNode slow = head;
        ListNode fast = head;

        // 使用快慢指针判断链表中是否存在环
        while (fast != null && fast.next.next != null) {
            slow = slow.next;  // 慢指针每次移动一步
            fast = fast.next.next;  // 快指针每次移动两步

            if (slow.val == fast.val) {  // 如果快慢指针相遇，则说明链表中存在环
                return true;
            }
        }

        return false;  // 快指针达到链表末尾，说明链表中不存在环
    }
}

• 在每一次循环中，快指针 fast 移动两步，慢指针 slow 移动一步。
• 如果快指针 fast 追上了慢指针 slow，那么链表中存在环，返回 true。
• 如果快指针 fast 移动到了链表的末尾（即指向空节点），那么链表中不存在环，返回 false。

该题考察的主要知识点是链表和快慢指针。

1. 链表：链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以分为单链表、双链表和循环链表等形式。
2. 快慢指针：快慢指针是指在解决一些链表相关问题时，定义两个指针分别按不同速度遍历链表。通常情况下，快指针每次移动两步，而慢指针每次移动一步。通过快慢指针的相对移动，可以判断链表是否存在环、找到环的起点、判断链表的中点等。