环形链表1

??给你一个链表的头节点 head ，判断链表中是否有环。
??如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。否则，返回 false

在这里插入图片描述

解法：

??利用Set集合的无重复值，唯一性去判断结点是否重复是最简单有效的办法。如果能添加则证明无环，若是无法添加，代表有一样的结点，所以有环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode p=head;
        Set<ListNode> set=new HashSet<ListNode>();
        while(p!=null){
            if(!set.add(p))
                return true;
            p=p.next;
        }
        return false;
    }
}

环形链表2

??给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
??如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。

在这里插入图片描述

解法一：Set集合

??因为要返回的是一个结点，所以每次p=p.next前，我们都要将值赋值出去。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode p=head;
        ListNode q=head;
        Set<ListNode> set=new HashSet<ListNode>();
        while(p!=null){
            q=p;
            if(!set.add(p)){
                return q;
            }
            p=p.next;
        }
        return null;
    }
}

解法二：Set集合优化

??因为它是每次p=p.next前都会判断一下是否存在，所以不需要提前赋值出去

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}