判断链表是否有环

1. 快慢指针法

实现思路：起初，快指针和慢指针一起指向头结点。快指针每次走2步，慢指针每次走1步，直到走到尾结点。若快慢指针相遇，说明链表中有环；若不相遇，说明链表中无环。

public class Solution{
    public boolean hasCycle(ListNode head){
        if(head == null) return false;
        ListNode p = head, q = head;
        while(p.next != null && p.next.next != null && q.next != null){
            p = p.next.next;
            q = q.next;
            if(p == q){
                return true;
            }
        }
        return false;
    }
}

2. 哈希表法

实现思路：通过检查一个节点此前是否被访问过来判断链表中是否有环。访问每一个节点，将它的引用存储到哈希表中。

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