牛客题解

分析：

链表中一道比较经典的题目了，注意正确理解题目所给的条件：

• 第一部分为一个链表。
• 第二部分为一个整数，-1代表该链表没有环，其他非负整数表示链表尾连接到链表中的位置（索引从 0 开始）
• 方法参数中，这个整数并不可见，仅仅是作为一个实际标识情况

解法一：哈希表

具体思路

• 创建一个Set集合，用于存放链表结点

• 只要head!=null

• 从链表头节点开始，将head加入set

• head = head.next

• 如果加入失败，说明该结点已经存在，即证明链表存在环

  手绘图解

Java参考代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
import java.util.*;
public class Solution {
    public boolean hasCycle(ListNode head) {
        //创建集合
        Set<ListNode> set = new HashSet<ListNode>();
        while(head!=null){
            //判断是否有环
            if(!set.add(head)){
                return true;
            }
            //下一个结点
            head = head