首页 > 试题广场 >

判断链表中是否有环

[编程题]判断链表中是否有环
  • 热度指数：498866 时间限制：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，点此查看相关信息
算法知识视频讲解
添加回答
Python
tsjlbb头像 tsjlbb 
class Solution:
    def hasCycle(self , head ):
        # write code here
        f = head
        s = head
        while f !=None and f.next != None:
            f = f.next.next
            s = s.next
            if s == f:
                return True
        return False
双指针 快慢跑，如果有环则快指针迟早会追上慢指针，如果没有环则快指针先走到最后，考虑到这两点就很好做了
发表于 2021-06-09 20:26:04 回复(0)
Python
周敬水头像 周敬水
简明易懂 Python双指针 
class Solution:
    def hasCycle(self , head ):
        # write code here
        if head == None&nbs***bsp;head.next == None:
            return False
        
        slow = head
        fast = head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False
发表于 2021-05-19 12:06:05 回复(0)
Python
wengJJ头像 wengJJ
Python
当存在环的情况下，快指针index= 2i%n，慢指针index=i%n，其中n为环中节点数
由公式可知当i等于n时，快指针和慢指针可相遇，所以这就解释了为啥存在环时，快慢指针会相遇
注意题目的空间复杂度为O(1), 使用list来存储遍历过的节点的方法，空间复杂度是O(n) 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 
# @return bool布尔型
#
class Solution:
    def hasCycle(self , head ):
#         快慢指针 空间复杂度为O(1) 符合题意
        p_slow=head
        p_fast=head
        while p_fast!=None and p_fast.next!=None:
            p_slow = p_slow.next
            p_fast = p_fast.next.next
            if p_slow==p_fast:
                return True
        return False
#         v_nodes 导致空间复杂度变为O(n)不符合题意
#         v_nodes = []  
#         p = head
#         while p and p.next:
#             if p.next in v_nodes: 
#                 return True
#             v_nodes.append(p)
#             p = p.next
#         return False



发表于 2021-04-18 13:00:16 回复(0)
Python
lyy~hhh头像 lyy~hhh
#法一：用哈希表
        #分析：依次遍历链表，遍历到的节点依次压入哈希表，若无环，则遍历到None，环中没有重复节点
        #若有环，则表中有重复元素，且第一个重复的节点就是入环节点
        #法二：用快慢指针
        #分析：快指针一次走两步，慢指针一次走一步；从头部开始遍历链表，若无环，则快指针会提前遍历到None
        #若有环，则快慢指针会在环中相遇；此时让快指针再次从头部开始遍历，每次改为走一步，
        #慢指针从相遇节点开始同步遍历，再次相遇的第一个节点就是入环节点
        if (head == None) or (head.next == None) or (head.next.next == None):
            return False
        fast = head.next.next
        slow = head.next
        while slow != fast :
            if (fast.next == None) or (fast.next.next == None):
                return False
            fast = fast.next.next
            slow = slow.next
        return True
#          code1.符合直觉
#         if head == None:
#             return False
#         fast = head
#         slow = head
#         while (fast != None) and (fast.next != None) and (fast.next.next != None):
#             fast = fast.next.next
#             slow = slow.next
#             if slow == fast:
#                 return True
#         return False

发表于 2021-04-03 21:08:08 回复(0)
Python
wwra头像 wwra
我大概看了一下没有我这么做的，我的方法更暴力简单，每次遍历一个数据，就把那个节点的val值换成None，然后一直遍历直到遇到节点为None或者节点的val为None为止，因为输入里似乎没有val为None的情况，所以直接判断退出循环的原因即可判断。 
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

#
#
# @param head ListNode类
# @return bool布尔型
#
class Solution:
    def hasCycle(self , head ):
        if head==None&nbs***bsp;head.next==None:
            return False
        while head.val!=None and head!=None:
            head.val=None
            head=head.next
        if head.val==None:
            return True
        else:
            return False


发表于 2021-03-22 17:17:12 回复(0)
Python
猫牛头像 猫牛 
class Solution:
    def hasCycle(self , head ):
        # write code here
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast is None:
                return False
            elif fast is slow:
                return True


发表于 2021-03-07 19:15:33 回复(0)
Python
splwany头像 splwany 
class Solution:
    def hasCycle(self , head ):
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                return True
        return False

编辑于 2021-03-05 14:04:14 回复(0)
Python
Hwhcz头像 Hwhcz 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 
# @return bool布尔型
#
class Solution:
    def hasCycle(self , head ):
        nodes = []
        while head:
            if head not in nodes:
                nodes.append(head)
                head = head.next
            else:
                return True
        return False

发表于 2021-02-23 17:46:34 回复(0)
Python
强人锁篮头像 强人锁篮 
class Solution:
    def hasCycle(self , head ):
        # write code here
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

发表于 2021-02-07 19:56:15 回复(0)
Python
崔崔呀头像 崔崔呀
因为面试面到这道题了，所以特意又来回顾一遍，再来体会一下快慢指针：
第一遍的时候一直奇怪为什么快2步不是快3步或其他步呢？
走三步也是可以，只是效率上比走两步会低，所以我们还是选择走两步：
class Solution: 
    def hasCycle(self , head ):
        # write code here
        if not head:
            return False
        fast=head
        slow=head
        while (fast is not None and fast.next is not None):
            fast=fast.next.next
            slow=slow.next
            if(fast==slow):
                return True
        return False



发表于 2021-02-06 19:34:26 回复(0)
Python
牛客219664531号头像 牛客219664531号 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 
# @return bool布尔型
#
class Solution:
    def hasCycle(self , head ):
        if not head:
            return False
        p1 = p2 = head
        while p2 and p2.next:
            p1 = p1.next
            p2 = p2.next.next
            if p1 == p2:
                return True 
        return False
        # write code here
快慢指针可以判断是否存在环，若存在环，快指针和慢指针一定会相遇，否则快指针还会率先到达链表末尾
发表于 2021-01-19 17:12:09 回复(0)
Python
牛客826863569号头像 牛客826863569号 
class Solution:
    def hasCycle(self, head):
        if not head:
            return False 

        slow = head 
        fast = head.next 

        while fast and fast.next:
            if fast ==slow:
                return True 
            slow = slow.next 
            fast = fast.next.next
            
        return False


编辑于 2020-12-14 09:44:24 回复(0)
Python
NovePlantimu头像 NovePlantimu
class Solution:
    def hasCycle(self , head ):
        # write code here
        # head始终没有变
        cur = head
        while cur:
            cur_next = cur.next
            if cur_next is head:
                return True
            cur.next = head   #这一步不能理解，把cur.next都指向链表头，这又不一定是个环形链表？为啥可以这么写？看了很久都没有看懂
            cur = cur_next
        return False
        # write code here
编辑于 2020-11-02 22:10:25 回复(0)
Python
黄沙遮天头像 黄沙遮天
快慢指针的思想解决此题目，慢指针每次只走一步，快指针每次走两步，如果进入环中的话，他们两者肯定会相遇且在慢指针在环中走的距离小于等于环的长度的情况下 
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
#
# @param head ListNode类
# @return bool布尔型
#
class Solution:
    def hasCycle(self, head):
        # write code here
        slow=fast=head
        while(fast and fast.next):
            slow=slow.next
            fast=fast.next.next
            if slow==fast:
                return True
        return False


发表于 2020-09-17 22:14:30 回复(0)
Python
FW.头像 FW. 
class Solution:
    def hasCycle(self, head):
        slow, fast = head, head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if slow == fast: return True
        return False

发表于 2020-09-16 17:39:27 回复(0)
提交观点

问题信息

链表 哈希 双指针
难度：
16条回答 48462浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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