首页 > 试题广场 >

判断链表中是否有环

[编程题]判断链表中是否有环
  • 热度指数：481567 时间限制：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，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
Python3
kyrisyuuuuu头像 kyrisyuuuuu
class Solution:
def hasCycle(self , head: ListNode) -> bool:
set_node = set()
while head:
if head in set_node:
return True
set_node.add(head)
head = head.next
return False
编辑于 2024-04-02 23:28:42 回复(0)
Python3
沉稳的袋鼠躺平又起来了头像 沉稳的袋鼠躺平又起来了
要满足两个限制条件应该只能搞破坏了吧，不然要么空间超，要么时间超
class Solution:
    def hasCycle(self , head: ListNode) -> bool:

        while True:
            if head == None:
                return False
            else:
                if head.next==None:
                    return False
                else:
                    if head.val == 0.1:
                        return True
                    head.val = 0.1
                    head = head.next
发表于 2024-03-18 16:41:10 回复(0)
Python3
想潜水的中国人在喝茶头像 想潜水的中国人在喝茶 
class Solution:
    def hasCycle(self , head: ListNode) -> bool:
        slow, fast = head, head
        while slow and fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow and fast and slow == fast:
                return True
        return False
编辑于 2024-02-05 20:13:03 回复(0)
Python3
leoncongyuwang头像 leoncongyuwang
用哈希表空间复杂度为O(n)不符合要求。
用双指针确实不错。
还有一种hack是写一个特殊值进val： 
class Solution:
    def hasCycle(self , head: ListNode) -> bool:
        if head is None:
            return False
        while head.next is not None:
            head.val = 123894612
            head = head.next
            if head.val and head.val == 123894612:
                return True

        return False




发表于 2023-10-12 23:39:23 回复(0)
Python3
牛客956196272号头像 牛客956196272号
1、数组： 
class Solution:
    def hasCycle(self , head: ListNode) -> bool:
        a = []
        while head:
            a.append(head)
            head = head.next
            if head in a:
                return True
        return False 
2、快慢指针： 
class Solution:
    def hasCycle(self , head: ListNode) -> bool:
        if not head:
            return False
        lead= head.next
        while head and lead and lead.next:
            if lead == head:
                return True
            head = head.next
            lead = lead.next.next
        return False



发表于 2023-04-28 10:15:25 回复(0)
Python3
snowy_shanghai头像 snowy_shanghai 
    def hasCycle(self , head: ListNode) -> bool:
        lis = []
        p = head
        while p:
            if p not in lis:
                lis.append(p)
                p = p.next
            else:
                return True
        return False

发表于 2023-03-02 00:31:12 回复(0)
Python3
西南第一深情头像 西南第一深情 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# @param head ListNode类 
# @return bool布尔型
#思路：
#1.顺序读取每一个节点
#2.若读取的节点不在已读节点列表中，继续读取下一个节点，直至到链表尾
#3.如果读取的节点在已读节点列表中，返回True
class Solution:
    def hasCycle(self , head: ListNode) -> bool:
        lst = []
        p = head
        while p:
            if p not in lst:
                lst.append(p)
                p = p.next
            else:
                return True
        return False

发表于 2022-12-10 14:50:16 回复(1)
Python3
我也很努力的在学了头像 我也很努力的在学了
这样算不算作弊哈哈
class Solution:
    def hasCycle(self , head: ListNode) -> bool:
        if head==None:
            return False
        i=1
        while(head!=None):
            if i >10000:
                return True
            head=head.next
            i+=1
        return False
发表于 2022-10-17 10:40:09 回复(1)
Python3
慢热的大白菜头像 慢热的大白菜 
class Solution:
    def hasCycle(self , head: ListNode) -> bool:
        visit={}
        p=head
        while p!=None:
            if visit.get(hash(p)):
                return True
            visit[hash(p)]=1
            p=p.next
        return False

发表于 2022-08-30 13:26:56 回复(0)
Python3
超级小兵头像 超级小兵
用哈希表就解决了，之前在lc上面刷过 
class Solution:
    def hasCycle(self , head ):
        # write code here
        dic=set()
        while head:
            if head in dic:
                return True
            dic.add(head)
            head = head.next
        return False


发表于 2021-08-22 12:07:42 回复(1)
Python3
King417头像 King417
class Solution:
    def hasCycle(self , head ):
        # write code here
        slow = head
        fast = head
        while (fast != None and fast.next != None):
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                return True
        return False
发表于 2021-07-17 08:27:02 回复(1)
提交观点

问题信息

链表 哈希 双指针
难度：
12条回答 47571浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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