《链表篇》---环形链表

题目传送门 

方法一：哈希表

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> visited = new HashSet<ListNode>();

        while(head != null){
            visited.add(head);
            head = head.next;
            if(visited.contains(head)){
                return true;
            }
        }
        return false;
    }
}

方法二：快慢指针

1.如果没有节点或只有一个节点，返回false。

2.定义一个快指针，一个慢指针。在快指针不等于慢指针的情况下，慢指针走一步，快指针走两步。

3.若快指针走到了最后一个节点，或者最后的空节点。说明没有环，返回false。

4.若有环，则快指针必定会被慢指针追上。因此若相等则返回true。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        
        ListNode slow = head;
        ListNode fast = head.next;

        while(slow != fast){
        if(fast == null || fast.next == null){
            return false;
        }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}