首页 > 试题广场 >

判断链表中是否有环

[编程题]判断链表中是否有环
  • 热度指数：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，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
C
徐文达头像 徐文达 
#include <stdbool.h>

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) 
{
    //没有结点，更不存在环
    if(!head)
    {
        return false;
    }    

    ListNode* slow = head;
    ListNode* fast = head;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        
        if(fast == slow)
        {
            return true;
        }
    }
    return false;
}

发表于 2024-03-30 11:05:33 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
bool hasCycle(struct ListNode* head) {
    struct ListNode *buffer[10000], *p1=head;
    int bufferLen=0;
    if(head==NULL)
        return false;
    while(p1->next!=NULL) {
        int i;
        for(i=0;i<bufferLen;i++) {
            if(p1==buffer[i])
                return true;
        }
        buffer[i] = p1;
        bufferLen++;
        p1 = p1->next;
    }
    return false;
}

编辑于 2024-03-15 12:15:43 回复(0)
C
想去杭州的高级磨洋工在学习头像 想去杭州的高级磨洋工在学习
#include <stdbool.h>
bool hasCycle(struct ListNode* head ) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast&&slow)
    {
        if(fast->next==NULL)
        {
            return false;
        }
        fast = fast->next->next;
        slow = slow->next;
        if(fast==NULL)
        {
            return false;
        }
        if(fast==slow)
        {
            return true;
        }
    }
    return false;
}
发表于 2024-03-01 20:56:13 回复(1)
C
无名珠头像 无名珠 
bool hasCycle(struct ListNode* head ) {
    //快慢指针
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while (fast!=NULL && slow!=NULL) 
    {
        if (fast->next!=NULL)
        {
            fast = fast->next->next; //快指针每次2步
        } 
        else 
        {
            return false;
        }
        slow = slow->next; //慢指针每次1步
        if (fast==slow) 
        {
            return true;
        }
    }    
    return false;
}

发表于 2023-08-19 20:41:40 回复(0)
C
小牛牛￥头像 小牛牛￥
#include <stdbool.h>
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

/**
 *
 * @param head ListNode类
 * @return bool布尔型
 */
bool hasCycle(struct ListNode* head )
{
    if (head == NULL) {
    return false;
    }
    struct ListNode *fast = head;
    struct ListNode *low = head;
    while (low->next && fast->next != head)
    {
        fast = fast->next->next;
        low = low->next;
        if (fast == low)
        {
            return true;
        }
    }
    return false;
   
}
发表于 2023-08-05 10:06:47 回复(0)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
bool hasCycle(struct ListNode* head )
{
    // write code here
    if(head)
    {
        struct ListNode*fast=head;
        struct ListNode*slow=head;
        do
        {
            if(!fast||!fast->next)
            {
                return false;
            }
            slow=slow->next;
            fast=fast->next->next;
        }
        while(fast!=slow);
        return true;
    }

    return false;
}
发表于 2023-07-04 09:46:52 回复(0)
C
牛客885968742号头像 牛客885968742号 
bool hasCycle(struct ListNode* head ) {
    struct ListNode*p1=head,*p2=head;
    while(p1&&p2){
        p1=p1->next;
        p2=p2->next;
        if(p2) p2=p2->next;
        if(p1==p2&&p1) return true;
    }
    return false;

发表于 2023-03-17 22:02:13 回复(0)
C
lijd头像 lijd 
#include <stdbool.h>
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
bool hasCycle(struct ListNode* head ) {
    // write code here

    int  i = 0;

    while (head && i <= 10000) {
        i++; head = head->next;
    }
    
    if (i > 10000) {
        return  true;
    }

    return  false;
}

发表于 2023-01-16 16:53:15 回复(0)
C
厚礼谢头像 厚礼谢
#include <stdbool.h>
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
bool hasCycle(struct ListNode* head ) {
    // write code here
    
    struct ListNode *fast = head;
    struct ListNode *slow = head;
    if(head == NULL || head->next == NULL)
    {
        return false;
    }
    while(fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
            return true;
        if(fast == NULL)
            return false;
    }

    return false;
}
发表于 2022-11-12 21:03:53 回复(0)
C
伦斯头像 伦斯 
bool hasCycle(struct ListNode* head) {
    for (int k = 0;; k++) {
        if (head == NULL)return false;
        head = head->next;
        if (k > 10001)return true;
    }
这题是搞笑吗？？？
发表于 2022-11-09 21:22:44 回复(3)
C
取nm名字全被取了头像 取nm名字全被取了 
bool hasCycle(struct ListNode* head ) 
{
    struct ListNode *p = head;
    struct ListNode *q = head;
    while(q && q->next && q->next->next)
    {
        p = p->next;
        q = q->next->next;
        if(q == p)
        {
            return true;
        }
    }
    return  false;
    // write code here
    
}

发表于 2022-11-02 21:18:36 回复(0)
C
Hayaizo头像 Hayaizo 
bool hasCycle(struct ListNode* head ) {
    if(head==NULL){
        return false;
    }
    struct ListNode*fast=head;
    struct ListNode*slow=head;
    while(fast!=NULL&&fast->next!=NULL){
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow){
            return true;
        }
    }
    return false;
}

发表于 2022-09-08 22:27:46 回复(0)
C
冬xur头像 冬xur 
bool hasCycle(struct ListNode* head ) {
    // write code here
    
    if(head==0||head->next==0){
        return false;
    }
    
    struct ListNode* p0=head;
    struct ListNode* p1=head;
    int i=0,j=0;
    
    while(p1!=0){
        p1=p1->next;i++;
        while(p0!=p1){
            j++;p0=p0->next;
        }
        if(j!=i){
            return true;
        }
        j=0;p0=head;
    }
    return false;
}

发表于 2022-08-18 21:17:13 回复(0)
C
牛客959866716号头像 牛客959866716号
//能不能帮忙看下哪里错啦！提交时显示段错误!有四个案例通不过
bool hasCycle(struct ListNode* head ) {
    // write code here
    struct ListNode * p;
    p=head;
    while(1)
    {
         
        if(!p)
            return
             false;
        p->val=-3;
        p=p->next;
        if(p->val==-3)
            break;
    }
    while(1)
    {
        if(!p)
            returnfalse;
        p->val++;
        p=p->next;
        if(p->val>-2)
            returntrue;
    }
}
发表于 2022-07-29 11:40:41 回复(1)
C
菜团子鼠鼠头像 菜团子鼠鼠 
bool hasCycle(struct ListNode* head ) {
    // write code here
    if(head == NULL )
    {
        
        return false;
    }
    struct ListNode*p = head;
    struct ListNode*q = head;
    
    while(p != NULL && p->next !=NULL)
    {
        p = p->next->next;//快慢指针，p走两步，q走一步
        q = q->next;
        if(q == p)//相遇则有环
        {
            return true;
        }
    }
    return false;
}

发表于 2022-07-22 19:31:54 回复(0)
C
牛客572130657号头像 牛客572130657号
逐个删除
bool hasCycle(struct ListNode* head ) {
    if(!head||!head->next)  return false;
    struct ListNode *cur1=head;
    struct ListNode *new1=head;
    while(new1->next){    
        new1=new1->next;   
        cur1->next=cur1;       //每次让当前节点指向当前节点
        if(new1->next==new1) return true;   //如果有环路 必有新节点的下一个节点指向新节点
        cur1=new1;
    }
    return false;
}
发表于 2022-05-22 17:42:55 回复(0)
C
牛客642829707号头像 牛客642829707号 
#include <stdbool.h>
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
bool hasCycle(struct ListNode* head ) {
    // write code here
    struct ListNode* slow=head;
    struct ListNode* fast=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
            return true;
    }
    return false;
}

发表于 2022-05-15 17:02:53 回复(0)
C
牛客680054381号头像 牛客680054381号
建议直接梭哈，空运行10001次，没有访问到表尾就是有环 
bool hasCycle(struct ListNode* head ) {
    // write code here
    int count = 0;
    struct ListNode* work = head;
    while (work != NULL && count < 10001) {
        work = work->next;
        count ++;
    }
    if (work == NULL) {
        return 0;
    } else {
        return 1;
    }
}


发表于 2022-04-30 11:24:48 回复(0)
C
阿金要努力头像 阿金要努力 
bool hasCycle(struct ListNode* head ) 
{
    // write code here
    struct ListNode* fast=head,*slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            return true;
        }
    }
    return false;
}

发表于 2022-04-24 13:24:30 回复(0)
C
牛客278153310号头像 牛客278153310号 
bool hasCycle(struct ListNode* head ) {
    // write code here
    struct ListNode *p,*q;
    p=q=head;
    //p->val=p->val+300000;
    if(!head) return false; 
    while(1){
        if(p->next==NULL)
            return false;
        if(p->next->val>=150000)
            return true;
        p->val=p->val+300000;
        p=p->next;
    }
}
访问过就给他加300000，后面如果碰到就表明已经访问过了，简单明了

发表于 2022-03-30 12:42:51 回复(0)
提交观点

问题信息

链表 哈希 双指针
难度：
33条回答 47570浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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