已知一个链表,计算并返回环形链表中环的长度,若无环则返回0 C语言代码
时间: 2024-09-30 16:05:20 浏览: 50
c语言基础-c语言编程基础之链表操作示例-环形链表.zip
在C语言中,我们可以使用快慢指针法来解决环形链表中环的长度问题。这种方法的基本思想是让两个指针分别以不同的速度遍历链表。如果链表有环,快指针每次走两步,慢指针每次走一步,最终两者会在环的某个位置相遇;如果没有环,则快指针会先到达链表的末尾。
下面是简单的C语言代码示例:
```c
#include <stdio.h>
#include <stdbool.h>
// 定义链表节点结构体
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 判断链表是否有环
bool hasCycle(ListNode* head) {
if (head == NULL || head->next == NULL) return false;
ListNode* slow = head;
ListNode* fast = head->next;
while (slow != fast) {
if (fast == NULL || fast->next == NULL) return false; // 如果快指针到头了还没碰到慢指针,说明无环
slow = slow->next;
fast = fast->next->next; // 快指针前进两步
}
return true;
}
// 计算环的长度,假设已经确认链表有环
int getCycleLength(ListNode* head) {
if (!hasCycle(head)) return 0; // 环不存在,直接返回
ListNode* slow = head;
ListNode* fast = head;
int length = 0;
while (fast != slow) { // 当两个指针再次相遇时,它们已经在环里走了length次
fast = fast->next;
length++;
}
return length;
}
int main() {
// 测试案例
// 这里需要你自己构建一个链表实例,并设置环
ListNode *head = ...;
bool hasRing = hasCycle(head);
if (hasRing) {
printf("环的长度: %d\n", getCycleLength(head));
} else {
printf("链表无环\n");
}
return 0;
}
```
阅读全文