题解 | #判断链表中是否有环#

import java.util.*;
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        return hasCycle1(head);
        //return hasCycle2(head);
    }

    public boolean hasCycle1(ListNode head) {
        if(head == null) {
            return false;
        }
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            //慢指针每次走一步
            slow = slow.next;
            //快指针每次走两步
            fast = fast.next.next;
            //如果相遇，说明有环，直接返回true
            if(slow == fast) {
                return true;
            }
             
        }

        return false;
    }

    public boolean hasCycle2(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode node = head;
        while (node != null) {
            //如果重复出现说明有环
            if (set.contains(node))
                return true;
            //否则就把当前节点加入到集合中
            set.add(node);
            node = node.next;
        }

        return false;
        
    }
}