# 判断单链表是否有环的两种方法

```#include <stdio.h>
#include <stdlib.h>

#define LEN 8
typedef struct node* node_t;

struct node{
char val;
struct node *next;
};

//method 1
//method 2

int main()
{
node_t* arr = (node_t*)malloc(sizeof(struct node)*LEN);
arr[0] = (node_t)malloc(sizeof(struct node));
int i;
for(i = 1; i < LEN; i++)
{
arr[i] = (node_t)malloc(sizeof(struct node));
arr[i - 1]->next = arr[i];
}
arr[LEN - 1]->next = NULL;

//you can add a loop here to test
//arr[6]->next = arr[0];
if (has_loop(arr[0]))
printf("method1: has loop.\n");
else
printf("method1: has no loop.\n");

if (has_loop2(arr[0]))
printf("method2: has loop.\n");
else
printf("method2: has no loop.\n");

return 0;
}

//if two pointer are equal, but they don't have the same steps, then has a loop
{
int pos1 = 0;
while(cur1){
int pos2 = 0;
pos1 ++;
while(cur2){
pos2 ++;
if(cur2 == cur1){
if(pos1 == pos2)
break;
else
return 1;
}
cur2 = cur2->next;
}
cur1 = cur1->next;
}
return 0;
}

//using step1 and step2 here
//if exists a loop, then the pointer which use step2 will catch up with the pointer which uses step1
{
while (p != NULL && q != NULL)
{
/*
p = p->next;
if (q->next != NULL)
q = q->next->next;
if (p == q)
return 1;
*/
//correct it on 17/11/2012
p = p->next;
q = q->next;
if (q != NULL)
q = q->next;
if (p != NULL && p == q)
return 1;
}
return 0;
}```

0 条评论

• ### Webpack创建、运行vue.js项目及其目录结构详解

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

• ### Keras-RetinaNet训练自己的数据详细教程

1、代码开源框架使用的是 fizyr/keras-retinanet 2、Keras版本要2.2.4以上

• ### 深入理解并发/并行，阻塞/非阻塞，同步/异步

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

• ### Generator的正确打开方式

代码运行后，我们首先会得到一条cooking的log， 然后在3s后会再次得到一条log。

• ### python高级特性-生成器

在每次调用next()的时候执行，遇到yield语句返回，再次执行时从上次返回的yield语句处继续执行。

• ### Top K问题

如果你对上述两者的原理有所了解,可以继续往下看.如果不了解,可以点击链接先看一下基础~.