判断链表是否有环(LeetCode141.环形链表)

题目

给定一个链表，判断链表中是否有环。

解析

题目本身不困难在LeetCode中也是简单等级。简单的方法是使用HashMap存储每次遍历到的节点，当遍历了新节点时，去HashMap中匹配是否已经遍历过了，如果已经存在于HashMap中，证明链表有环。如果遍历的null节点则链表无环。
提供一个O(1)空间复杂度的算法，快慢指针法。定义两个指针，一个慢指针一次移动一步，另一个快指针一次移动两步。当链表中存在环时，快指针一定会再一次追上慢指针，此时表明链表中有环；如果慢指针或快指针有一个遍历到null节点，链表中无环。

代码

public boolean hasCycle(ListNode head) {
    if(null == head){
        return false;
    }
    ListNode slowPointer = head;
    ListNode quickPointer = head;
    while(true){
        //慢指针走一步
        slowPointer = slowPointer.next;
        if(null == slowPointer){
            return false;
        }
        //快指针走两步
        quickPointer = quickPointer.next;
        if(null == quickPointer){
            return false;
        }
        quickPointer = quickPointer.next;
        if(null == quickPointer){
            return false;
        }
        //快指针追上慢指针则有环
        if(slowPointer == quickPointer){
            return true;
        }
    }
}