C++ 实现：环形链表环长度计算与起始位置确定全解析

以下是一个用 C++ 实现计算环形链表环的长度和确定环起始位置的示例代码： ```cpp #include <iostream> // 链表节点结构体 struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(NULL) {} }; // 检测链表是否有环，并返回环的起始节点 ListNode* detectCycle(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) { ListNode* ptr = head; while (ptr!= slow) { ptr = ptr->next; slow = slow->next; } return ptr; } } return NULL; } // 计算环的长度 int lengthOfCycle(ListNode* head) { ListNode* start = detectCycle(head); if (start == NULL) { return 0; } ListNode* curr = start->next; int length = 1; while (curr!= start) { length++; curr = curr->next; } return length; } int main() { // 构建测试链表 ListNode* head = new ListNode(0); ListNode* p = head; for (int i = 1; i < 10; i++) { ListNode* ptmp = new ListNode(i); p->next = ptmp; p = ptmp; } p->next = head->next->next; // 制造环 int cycleLength = lengthOfCycle(head); std::cout << "环的长度: " << cycleLength << std::endl; return 0; } ``` 上述代码中，`detectCycle` 函数用于检测链表是否有环并返回环的起始节点。`lengthOfCycle` 函数基于 `detectCycle` 的结果计算环的长度。在 `main` 函数中构建了一个有环的测试链表，并调用相关函数进行计算和输出。 ######[AI写代码神器 | 519点数解答 | 2024-10-09 17:31:13]