环形链表_141_142

LeetCode_141：https://leetcode-cn.com/problems/linked-list-cycle/

　　给你一个链表的头节点 head ，判断链表中是否有环。

　　如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

　　如果链表中存在环 ，则返回 true 。 否则，返回 false 。

/*
解题思路：快慢指针
    定义两个指针p，q，都指向head;
    让p每次向前走一步，q每次向前走两步，
    如果成环，则它们会相遇，
    如果不成环，则不会。
*/
class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow.equals(fast)){
                return true;
            }
        }
        return false;
    }
}

/*
使用哈希表来存储所有已经访问过的节点。
每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。
重复这一过程，直到我们遍历完整个链表即可。
*/
class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}