C 语言：用快慢指针算法精准计算单链表中环的长度

以下是使用快慢指针的方法来计算链表中环的长度的算法思想： 1. 定义两个指针，一个快指针`fast`每次移动两步，一个慢指针`slow`每次移动一步。 2. 让两个指针从链表头开始移动，如果在移动过程中`fast`等于`slow`，则说明链表中有环，进入下一步；否则链表无环，返回环长为 0 。 3. 当找到环后，让`slow`指针不动，`fast`指针继续移动，直到再次等于`slow`指针，此时`fast`指针移动的次数就是环的长度。 以下是用 C 语言描述的代码框架： ```c #include <stdio.h> #include <stdlib.h> // 定义链表节点 typedef struct ListNode { int data; struct ListNode *next; } ListNode; // 创建新节点 ListNode* createNode(int data) { ListNode* newNode = (ListNode*)malloc(sizeof(ListNode)); newNode->data = data; newNode->next = NULL; return newNode; } // 计算环的长度 int getCycleLength(ListNode* head) { ListNode* slow = head; ListNode* fast = head; // 查找是否有环 while (fast!= NULL && fast->next!= NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) { int cycleLength = 1; fast = fast->next; while (fast!= slow) { cycleLength++; fast = fast->next; } return cycleLength; } } return 0; } int main() { // 构建测试链表，这里省略链表构建代码 ListNode* head = // 初始化链表头节点 int length = getCycleLength(head); printf("环的长度为: %d\n", length); return 0; } ``` 在实际使用中，您需要根据具体的需求完善链表的构建和其他相关部分的代码。 ######[AI写代码神器 | 489点数解答 | 2024-09-23 13:42:37]