c++实现环形链表的长度
时间: 2024-09-24 12:00:31 浏览: 11
在 C++ 中,环形链表(Circular Linked List)是一种特殊的链表结构,它的头节点指向最后一个节点,形成一个闭合的环。要计算环形链表的长度,你可以采用快慢指针的方法,也称为“龟兔赛跑”算法。
以下是基本步骤:
1. 初始化两个指针 `slow` 和 `fast`,分别设置为链表的头节点。
2. `slow` 指针每次移动一步,`fast` 指针每次移动两步。
3. 如果链表不是环形的,那么当 `fast` 指针到达 null(结束)时,`slow` 就会指向链表的尾部(非环部分的最后一个节点)。
4. 如果链表是环形的,当 `fast` 指针追上 `slow` 时,它们都在环内的某个位置。
5. 然后从 `slow` 开始,再次将它们都移动到下一个节点,同时计数,直到它们相遇,此时的步数就是环的长度。
下面是一个简单的 C++ 函数示例,用于计算环形链表的长度:
```cpp
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
int detectCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return 0; // 链表为空或只有一个节点,长度为0或1
}
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开始遍历找到环起点
ListNode* slow_ptr = slow;
ListNode* fast_ptr = head;
while (slow_ptr != fast_ptr) {
slow_ptr = slow_ptr->next;
fast_ptr = fast_ptr->next;
}
// 计算环长,从环起点开始,两者同时移动直到再次相遇
int length = 1;
slow = slow_ptr;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
length++;
}
return length;
}
}
return 0; // 非环形链表
}
```