已知一个链表,计算并返回环形链表中环的长度,若无环则返回0,用c语言实现
时间: 2024-09-24 13:14:20 浏览: 29
在C语言中,可以使用快慢指针法(Floyd's Tortoise and Hare Algorithm)来解决这个问题。快指针每次移动两步,慢指针每次移动一步,如果链表中有环,那么快指针最终会追上慢指针,它们相遇的地方就是环的起点。然后分别从链表头部开始计数两者到达环起点的距离,这个距离就是环的长度。
以下是C语言的一个基本实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
int getLengthOfCycle(ListNode* head) {
if (head == NULL || head->next == NULL) {
return 0; // 如果链表为空或者只有一个节点,说明没有环
}
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (fast == NULL || fast->next == NULL) {
return 0; // 指针之一到达了链表尾部,说明没有环
}
slow = slow->next;
fast = fast->next->next;
}
// 找到环的起点
ListNode* ptr1 = head;
ListNode* ptr2 = slow;
int length = 0;
while (ptr1 != ptr2) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
length++;
}
return length;
}
// 示例用法
int main() {
// 创建一个有环的链表...
ListNode* list = createLinkedListWithCycle(); // 自行实现创建链表函数
int ringLength = getLengthOfCycle(list);
printf("Ring length: %d\n", ringLength);
return 0;
}
```
在这个示例中,你需要提供`createLinkedListWithCycle()`函数来创建一个包含环的链表,这通常涉及到修改链表节点的next指针来形成环。