用c++计算循环链表的长度
时间: 2024-09-29 08:08:54 浏览: 13
在C++中,计算循环链表(Circular Linked List)的长度需要遍历整个链表,因为链表头节点的next指针指向的是最后一个节点,形成了一个闭环。以下是一个简单的示例,展示了如何通过迭代或递归的方式来计算循环链表的长度:
**迭代法:**
```cpp
struct Node {
int data;
Node* next;
};
int getLength(Node* head) {
if (head == nullptr) return 0; // 空链表
int length = 1;
Node* current = head;
while (current->next != head) { // 循环直到回到起点
length++;
current = current->next;
}
return length;
}
```
在这个例子中,我们首先检查头节点是否为空,然后从头开始逐个移动到下一个节点,直到再次遇到头节点,此时链表已经遍历完毕。
**递归法:**
```cpp
int getLength(Node* head) {
if (head == nullptr || head->next == head) return 0; // 空链表或非循环链表
Node* tail = head;
while (tail->next != head) {
tail = tail->next;
}
// 尾指针现在指向链表的起点,所以递归返回1加上剩余部分的长度
return 1 + getLength(tail->next);
}
```
这里我们使用了尾递归的方式,找到链表的起点,然后递归地计算剩余部分的长度加上起点本身。