C++已知一个链表,计算并返回环形链表中环的长度,若无环则返回0。
时间: 2024-10-17 11:10:20 浏览: 34
在C++中,检测链表是否有环并计算环的长度可以采用“快慢指针”(Floyd's Tortoise and Hare Algorithm)也称为“龟兔赛跑”算法。这个算法涉及到两个节点,一个移动一个单位,另一个移动两个单位。如果链表有环,那么这两个节点最终会相遇于环内的某个点;如果没有环,则其中一个会在到达链表末尾之前结束。
以下是基本步骤:
1. 定义两个指针,初始都指向链表头部。
2. 每次迭代时,正常节点前进一步,快节点前进两步。
3. 如果快节点到达了尾部(NULL),说明没有环,返回0。
4. 如果快节点和慢节点相遇,说明找到了环的起点,此时记下快节点的位置。
5. 将快节点恢复到慢节点的位置,并继续同时移动,直到再次相遇。两次相遇之间的距离就是环的长度。
在C++中,这通常需要一个辅助函数来跟踪环内节点的数量,例如计数器变量:
```cpp
size_t detectCycleLength(Node* head) {
if (head == nullptr || head->next == nullptr) return 0;
Node* slow = head;
Node* fast = head->next;
while (slow != fast) {
if (fast == nullptr || fast->next == nullptr) return 0; // 环不存在
slow = slow->next;
fast = fast->next->next;
if (fast == slow) { // 环存在
size_t len = 0;
slow = slow->next; // 移动慢指针进入环
while (slow != fast) {
slow = slow->next;
fast = fast->next;
len++;
}
return len;
}
}
// 环不存在
return 0;
}
```
阅读全文