c++求环形链表长度
时间: 2024-09-25 08:09:05 浏览: 11
在C++中,计算环形链表的长度可以采用迭代或递归的方式。这里是一个基本的迭代算法:
首先,我们需要定义两个指针,`p` 和 `q`,初始时都指向链表的头节点。然后让 `p` 每次前进一步,`q` 每步两步,如果它们相遇(即 `p == q`),说明找到了环的起点 `slow`。此时再让 `p` 回到头节点并开始移动,每次移动一步,`q` 继续移动两步,直到它们再次相遇。这时,`q` 的位置就是环长。
这里是伪代码:
```cpp
// 定义环形链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode* slow; // 储存环的起点
};
ListNode* detectCycle(ListNode* head) {
if (head == nullptr || head->next == nullptr) return nullptr;
ListNode* p = head;
ListNode* q = head;
while (q != nullptr && q->next != nullptr) {
p = p->next;
q = q->next->next;
if (p == q) { // 找到了环
p = head; // 将p重新置回头节点
while (p != q) { // 计算环的长度
p = p->next;
q = q->next;
}
break;
}
}
return p == nullptr ? nullptr : p;
}
```