java算法：判断链表是否有环_判断链表是否有环java

leetcode:141

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

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

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

       针对这个题目，我们有一个形象的比喻，就是在操场上你追我赶，如果有环形，那么跑的一快一慢的两个人在操场上跑，跑的快的迟早会再次与跑的慢的相遇。

       因此我们可以定义快慢两个指针，慢指针每走一步，快指针就走两步（或更多步），当快指针与慢指针重合的时候，就说明链表有环。

        代码如下，我们定义了slow和fast两个指针，从一开始让快指针指向慢指针的下一个节点。我们遍历链表来判断，以什么做为结束条件呢，因为fast比slow遍历的快，因此我们只需要判断fast不为null并且fast的下一个节点不为null为循环条件。每遍历一次，判断一下快慢两个节点是否相等，如果相等则链表有环，反之则没有。

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
       return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        if (slow == fast) {
           return true;
        }
        fast = fast.next.next;
        slow = slow.next;
    }
    return false;
}