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

判断链表是否有环

我们可以对链表的操作无非就是遍历，删除，增加，修改，很明显一般题目都是需要遍历链表，本题也不例外，让我们看看链表有环意味着什么，意味着按顺序遍历链表，会遇到至少一个元素访问两次，自然而然也就想到去重，对，就是Java里的HashSet就行，只要碰到相同元素，就可以判断链表是有环的。

但还有没有其它方法呢，改变一下思维，当链表有环时，遍历链表会死循环，永远不会结束遍历，这就相当于400米操场跑步，一直绕着跑道跑没有出口，有一个有意思的现象就是两个人如果匀速跑步，一快一慢，快的那一个一定会追上慢的一个，而且比慢的那个人跑多了若干圈，只要两个人能相遇，就说明操作是无限循环的，链表有环也是同样的道理，设定两个指针，一快一慢，如果快指针能到达链表末尾，就说明链表无环，如果有环，就一定会与慢指针相遇。

代码如下：

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 判断链表有环？如果可以使用额外空间用hashset去重特性可以表示，不可以使用额外空间的话，用快慢指针
        // 这里直接快慢指针好了
        if(head == null) return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while(true){
            if(slow == fast) break;
            if(fast == null || fast.next == null) return false;
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}