题解 | #牛牛队列成环# 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
        // 使用快慢指针判断链表中是否存在环
        ListNode slow = head; // 慢指针
        ListNode fast = head; // 快指针

        while (true) { // 进入循环，直到找到环或遍历完整个链表
            for (int i = 0; i < 2; ++i) { // 快指针每次前进两步
                fast = fast.next; // 快指针前进一步
                if (fast == null) { // 如果快指针到达链表尾部，说明没有环
                    return false;
                }
                if (fast.val == slow.val) { // 如果快慢指针的值相等，则存在环
                    return true;
                }
            }
            slow = slow.next; // 慢指针前进一步
        }
    }
}

该题知识点

1. 快慢指针：使用快慢指针的思路判断链表中是否存在环。快指针每次前进两步，慢指针每次前进一步，如果存在环，两个指针最终会相遇。
2. 链表的遍历：通过循环遍历链表，同时使用快慢指针来判断是否存在环。当快指针到达链表的尾部或快慢指针的值相等时，循环结束。
3. 边界条件处理：在循环中判断快指针是否到达链表尾部，如果到达则说明没有环，返回false。

代码解释：

1. 定义两个指针slow和fast，初始化为链表的头节点head。
2. 进入一个无限循环，直到找到环或遍历完整个链表。
3. 在每次循环中，快指针fast向前移动两步，慢指针slow向前移动一步。
4. 检查快指针fast是否为null，如果是，说明已经遍历到链表的尾部，不存在环，返回false。
5. 检查快慢指针所指节点的值是否相等，如果相等，说明存在环，返回true。
6. 如果以上条件都不满足，继续下一次循环，慢指针slow向前移动一步。

该代码使用了快慢指针的方法来判断链表中是否存在环。快指针每次前进两步，慢指针每次前进一步。如果存在环，快慢指针最终会相遇；如果不存在环，快指针会先到达链表尾部，此时可以确定没有环。

代码的时间复杂度为O(n)，其中n是链表的长度。在最坏情况下，需要遍历整个链表才能确定是否存在环。空间复杂度为O(1)，只使用了常数级别的额外空间。