一、简介

描述

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

二、解法

分析：双指针（快慢指针），若存在环，则快指针迟早会追上慢指针

实现如下：

/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
*/
func hasCycle( head *ListNode ) bool {
    // write code here
    if head == nil || head.Next == nil {
        return false
    }
    
    quickNode := head.Next // 每次移动两格
    slowNode := head // 每次移动1格
    
    for quickNode != nil {
        if quickNode == slowNode {
            return true
        }
        
        quickNode = quickNode.Next
        if quickNode != nil {
            quickNode = quickNode.Next
        }
        
        slowNode = slowNode.Next
    } 
    
    return false
}