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
           if (head == null) {
            return false;
        } else if (head.next == null) {
            return false;
        }

        ListNode slow = head; // 慢指针，每次前进一步
        ListNode fast = head.next; // 快指针，每次前进两步

        while (fast != null && fast.next != null) { // 判断快指针是否到达链表尾部
            if (slow.val == fast.val) { // 如果慢指针和快指针相遇，则存在环
                return true;
            }

            slow = slow.next; // 慢指针前进一步
            fast = fast.next.next; // 快指针前进两步
        }

        return false; // 快指针到达尾部，说明没有环，返回false
    }
}

考察的知识点是快慢指针技巧，通过设定不同速度的指针，检测链表是否存在环。在循环过程中，慢指针每次前进一步，快指针每次前进两步，如果存在环，快指针最终会追上慢指针。如果快指针到达链表尾部，则说明没有环。

1. 首先进行头节点和链表为空的判断，如果链表为空或只有一个节点，则直接返回false。
2. 设置两个指针slow和fast，分别指向头节点和头节点的下一个节点。
3. 进入循环，判断快指针是否到达链表尾部。如果快指针到达尾部，则说明链表没有环，返回false。
4. 在循环过程中，每次慢指针前进一步，快指针前进两步。如果慢指针和快指针相遇（即指向同一个节点），则存在环，返回true。
5. 循环结束后，快指针到达尾部，说明没有环，返回false。