检测单链表中是否有环(C语言)

方法：双指针法思路使用两个指针，两个初始时都指向链表的头结点，然后one指针一次加一，另一个two指针一次加二。在链表有环时，two指针与one指针相等就说明有环。当one指针到达环的起始位置时，two指针已经在环中，此时，由于是环的结构，相当于two指针在追one指针， 由于每two指针每次比one指针快一， 所以，one只需再走两个指针之间的距离的次数，two指针就可以追上one指针。距离小于环的长度。 最终的循环次数小于等于n，最坏情况为n次。所以，时间复杂度是O(n)。图解

链表中环检测算法图

当one指针进入环的初始点时，two指针可能已经在环循环多次，此时正好在图中的位置。此时，就可以看成是two指针在追one指针，由于two每次都比比one快1，所以，在图中1的位置可以判断，再经过5次移动，two和one就会处于同一个位置。演示结果与预期一致。代码

#include #include //构造结构体typedef struct list{int data;struct list *next;}*List,LNode;//函数声明List init_list(List head);int Detection(List head);void main(){ List head; head = (LNode*)malloc(sizeof(LNode)); head = init_list(head); if(Detection(head)) printf("单链表中有环!"); else printf("单链表中无环!"); }//链表初始化函数List init_list(List head){int i = 1;List p = head;while(i <= 8){List s;s = (LNode*)malloc(sizeof(LNode));s->data = i;s->next = NULL;p->next = s;p = p->next;i++;} p->next = head->next->next;return head->next;}//双指针检测单链表中是否有环int Detection(List head){ //0为无环，1为有环 List one = head; if(head->next == NULL) return 0; List two = head->next->next; while(two != NULL) { one = one->next; two = two->next->next; if(one == two) return 1; } return 0;}