首页 > 试题广场 >

判断链表中是否有环

[编程题]判断链表中是否有环
  • 热度指数：508054 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
判断给定的链表中是否有环。如果有环则返回true，否则返回false。


数据范围：链表长度 ，链表中任意节点的值满足
要求：空间复杂度 ，时间复杂度

输入分为两部分，第一部分为链表，第二部分代表是否有环，然后将组成的head头结点传入到函数里面。-1代表无环，其它的数字代表有环，这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。

例如输入{3,2,0,-4},1时，对应的链表结构如下图所示：

可以看出环的入口结点为从头结点开始的第1个结点（注：头结点为第0个结点），所以输出true。
示例1

输入

{3,2,0,-4},1

输出

true

说明

第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true
示例2

输入

{1},-1

输出

false

说明

第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false
示例3

输入

{-1,-7,7,-4,19,6,-9,-5,-2,-5},6

输出

true

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
Go
牛客204546834号头像 牛客204546834号
使用map保存走过的地址就行，每走过一个节点map[addr]int计数器加一,指针的地址为空则无环，count>=2则有环
func hasCycle( head *ListNode ) bool {
    // write code here
    count := make(map[*ListNode] int)
    ptr1 := new(ListNode)
    ptr1 = head
    flag := false
    for {
        if ptr1 == nil{
            flag = false
            break
        }
        count[ptr1]++
        if count[ptr1] >= 2{
            flag = true
            break
        }
        ptr1 = ptr1.Next
    }

    return flag
}

发表于 2024-08-10 16:58:37 回复(0)
Go
一条自洽的鱼头像 一条自洽的鱼
func hasCycle( head *ListNode ) bool {
    slice := make(map[*ListNode]bool)
    for{
        if head == nil {
            break
        }
        _, ok := slice[head]
        if(ok){
            return true
        }
        slice[head] = true
        head = head.Next
    }
    return false
}
发表于 2024-05-28 15:15:36 回复(0)
Go
qiao_头像 qiao_
没说不可以改节点值^^ 
func hasCycle( head *ListNode ) bool {
   cur := head for { if cur == nil { return false  } if cur.Val == 100001 { return true  }
      cur.Val = 100001  cur = cur.Next
   }
}

发表于 2022-08-03 19:58:31 回复(1)
Go
风轻云淡.头像 风轻云淡. 
func hasCycle( head *ListNode ) bool {
    if head==nil{
        return false
    }
    // write code here
    slow,fast:=head,head
    for fast!=nil{
        slow=slow.Next
        fast=fast.Next
        if fast==nil{
            return false
        }
        fast=fast.Next
        if slow==fast{
            return true
        }
    }
    return false
}

发表于 2022-04-17 13:11:14 回复(0)
Go
admxt头像 admxt
func hasCycle( head *ListNode ) bool {
    // write code here
    hit:=make(map[*ListNode]bool)
    for{
        if head ==nil{
            return false
        }
        if _,ok:=hit[head];ok{
            return true
        }else{
            hit[head]=true
            head=head.Next
        } 
    }
}
发表于 2022-02-24 17:54:23 回复(0)
Go
ALSRitter头像 ALSRitter 
func hasCycle( head *ListNode ) bool {
    if head == nil || head.Next == nil {return false}
    slow, fast := head, head.Next
    for fast != nil && fast.Next != nil {
        if fast.Val == slow.Val {
            return true
        }

        slow = slow.Next
        fast = fast.Next.Next
    }
    
    return false
}
快慢指针
发表于 2021-11-08 15:03:07 回复(0)
Go
CCXX201902121547196头像 CCXX201902121547196 
func hasCycle( head *ListNode ) bool {
    // write code here
    fast := head
    slow := head
    for fast != nil && fast.Next != nil{
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast{
            return true
        }
    }
    return false
}

发表于 2021-10-06 16:49:37 回复(1)
Go
王飞-6头像 王飞-6 
func hasCycle( head *ListNode ) bool {
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            return true
        }
    }
    return false
}

发表于 2021-09-08 16:47:05 回复(0)
Go
tttddd头像 tttddd 
func hasCycle( head *ListNode ) bool {
    // write code here    
    //快慢指针追赶
    if head==nil||head.Next==nil{
        return false
    }
    slow,fast:=head,head.Next.Next
    for fast!=nil{
        //追上了，有环
        if slow==fast{
            return true
        }
        slow=slow.Next
        //判断是否到链表尾部
        if fast.Next==nil{
            return false
        }
        fast=fast.Next.Next
    }
    return false
}
发表于 2021-07-15 16:30:04 回复(0)
提交观点

问题信息

链表 哈希 双指针
难度：
9条回答 49133浏览

热门推荐

通过挑战的用户

查看代码

相关试题

判断链表中是否有环

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号