计算并返回环形链表中环的长度c++
时间: 2024-10-17 09:10:10 浏览: 5
环形链表中的环长计算通常使用两个指针,一个快指针每次移动两步,另一个慢指针每次移动一步。当快指针追上慢指针时,两者都在环内的某个点。然后,我们可以将这两个指针都移到环的起点,让快指针继续前进直到再次追上慢指针。两次相遇的位置之差就是环的长度。
以下是C++的一个简单实现:
```cpp
class ListNode {
public:
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int detectCycleLength(ListNode* head) {
if (head == nullptr || head->next == nullptr) return 0; // 链表为空或只有一个节点
ListNode slow(*head);
ListNode fast(*head);
while (fast.next != nullptr && fast.next->next != nullptr) {
slow = slow.next;
fast = fast.next->next;
if (slow == fast) { // 如果找到交叉点
slow = head; // 将慢指针恢复到链表头
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
break;
}
}
if (fast == nullptr || fast->next == nullptr) return 0; // 没有环
else return fast->next - slow; // 返回环的长度
}
```
阅读全文