用c语言写已知一个链表,计算并返回环形链表中环的长度,若无环返回0 代码
时间: 2024-09-27 09:10:21 浏览: 5
在C语言中,我们可以使用快慢指针的方法来检测和计算环形链表的长度。快慢指针的思想是快指针每次走两步,慢指针每次走一步,如果链表有环,那么它们最终会在环内的某个点相遇;如果没有环,则快指针会先到达链表的尾部。
以下是一个简单的C语言函数,用于计算环形链表的长度:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
// Function to find the length of a circular linked list
int detectCycleLength(Node* head) {
if (head == NULL || head->next == NULL) {
return 0; // No cycle or empty list
}
Node* slow = head;
Node* fast = head->next;
while (slow != fast) {
if (fast == NULL || fast->next == NULL) {
return 0; // Fast pointer reaches end, no cycle
}
slow = slow->next;
fast = fast->next->next;
}
// Slow and fast pointers have met at the start of the cycle
slow = head;
int len = 1; // Start from first node
while (slow != fast) {
slow = slow->next;
fast = fast->next;
len++;
}
return len;
}
// Function to create a simple circular linked list with a loop for testing purposes
Node* createCircularList(int n, int* values) {
Node* head = (Node*)malloc(sizeof(Node));
head->data = values[0];
head->next = head; // Create a loop
for (int i = 1; i < n; ++i) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = values[i];
newNode->next = head->next;
head->next = newNode;
}
return head;
}
int main() {
int values[] = {1, 2, 3, 4, 5};
Node* head = createCircularList(5, values);
int cycleLength = detectCycleLength(head);
printf("Cycle length: %d\n", cycleLength);
free(head); // Don't forget to deallocate memory
return 0;
}
```
这个程序首先创建一个环形链表,然后使用`detectCycleLength`函数找出环的长度。注意,为了测试,你需要提供一个包含循环的链表结构。如果你没有这样的链表,你可以自己构造一个。