目录
判断链表中是否有环
访问量:222

一、简介

描述

判断给定的链表中是否有环。如果有环则返回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
}