C语言写一份成环检测算法
时间: 2023-05-27 11:01:45 浏览: 116
算法描述:
利用快慢指针判断一个链表是否成环,如果快指针能够追上慢指针,则链表存在环。
算法实现:
```
#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
int data;
struct Node* next;
}Node;
// 创建链表,返回头结点
Node* createList(int* arr, int n){
Node* head = (Node*)malloc(sizeof(Node));
head->data = -1;
head->next = NULL;
Node* p = head;
for(int i = 0; i < n; i++){
Node* node = (Node*)malloc(sizeof(Node));
node->data = arr[i];
node->next = NULL;
p->next = node;
p = p->next;
}
return head;
}
// 判断链表是否成环
int isCircle(Node* head){
Node* slow = head->next;
Node* fast = head->next;
while(fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
return 1;
}
}
return 0;
}
// 主函数
int main(){
int arr[] = {1,2,3,4,5};
int n = sizeof(arr)/sizeof(int);
Node* head = createList(arr, n);
//将链表的最后一个节点的指针指向第二个节点,形成环
Node* tail = head;
while(tail && tail->next){
tail = tail->next;
}
tail->next = head->next->next;
if(isCircle(head)){
printf("链表成环!\n");
}else{
printf("链表未成环!\n");
}
return 0;
}
```
算法解释:
该算法利用了快慢指针的特性,在遍历链表的过程中,慢指针每次向后移动一步,快指针每次向后移动两步,如果链表成环,那么快指针最终将追上慢指针。如果链表不成环,那么快指针最终将指向NULL,整个遍历过程将结束。