哈希表

有一种使用额外空间的做法,即使用哈希表
即遍历链表,然后把结点存储到HashSet中,然后检查HashSet中是否存在相同的结果,如果有的话即链表有环,否则没环。

通俗地讲,就是把遍历过的结点都存起来,以后每遍历一个结点都和已经存起来的结点进行比较,如果有重复则说明链表有环,“又回到最初的起点~”。

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while(head != null){
	    // 判断Set中是否有这个结点
            if(set.contains(head)){
                return true;
            }
	    // 把每个结点都放到Set中
            set.add(head);
            head = head.next;
        }
        return false;
    }
}

时间复杂度为$O(n)$
因为使用了额外的空间存储链表结点,所以空间复杂度为$O(n)$。


快慢指针

验证链表是否有环,可以用快慢指针的思想。

fast指针跑得快,一次走两步,slow指针跑得慢,一次走一步,如果有环,那么这两个指针一定会相遇。
因为fast跑得快,如果能走到尽头(即遇到null了),那肯定没有环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        ListNode fast = head.next, slow = head;
	// 遍历判断两指针是否能重合,即fast是否追上了slow
        while(fast != slow){
	    // 走到“尽头”了,链表没有环
            if(fast == null || fast.next == null){
                return false;
            }
	    // fast指针一次走两步,slow指针一次走一步
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}

时间复杂度$O(n)$,空间复杂度$O(1)$。