C++循环链表递归节点计数的终止条件设置问询

嘿，这个问题戳中了循环链表递归的一个经典痛点——因为首尾相连，常规单链表靠NULL终止递归的思路完全走不通，得换个锚点来判断是否遍历完一圈。

先说说为什么常规思路失效：

常规单链表的递归计数逻辑是碰到NULL就返回0，但循环链表的尾节点next指针指向的是头节点，永远不会出现NULL，直接用这个条件会导致无限递归，最终栈溢出。

那正确的终止条件该怎么设计？核心思路是记住最初的头节点，当递归遍历到的节点回到这个初始头节点时，就说明已经绕链表走了一圈，该终止递归了。

结合你给出的示例函数结构，我们可以借助一个辅助递归函数来传递这个“初始头节点”的标记，具体实现如下：

// 对外的接口函数，和你给出的函数结构对齐
int count(node *head) {
    // 先处理空循环链表的边界情况
    if (head == NULL) {
        return 0;
    }
    // 调用辅助函数，从第一个节点的下一个节点开始遍历，同时传入原始头节点作为锚点
    // 加1是因为要把当前的头节点算进去
    return countHelper(head->next, head) + 1;
}

// 辅助递归函数，负责实际的计数逻辑
int countHelper(node *current, node *originalHead) {
    // 终止条件：当前节点回到了原始头节点，说明遍历完所有节点
    if (current == originalHead) {
        return 0;
    }
    // 递归计数：当前节点算1个，加上后续节点的计数
    return countHelper(current->next, originalHead) + 1;
}

代码解释： #

• 对外的count函数先处理空链表的特殊情况（虽然循环链表一般不会为空，但严谨性还是要有的）。
• 辅助函数countHelper的两个参数：current是当前遍历到的节点，originalHead是我们一开始的头节点（锚点）。
• 当current等于originalHead时，说明我们已经绕链表走了一圈，所有节点都数过了，此时返回0终止递归。
• 每一层递归都会把当前节点算入计数（加1），然后继续递归下一个节点。

如果你不想用辅助函数，有没有其他办法？比如用静态变量存储原始头节点，但这种方式非常不推荐——静态变量的生命周期是整个程序，如果你多次调用count函数，静态变量不会自动重置，会导致计数结果完全错误。

总结一下：循环链表递归计数的关键就是用原始头节点作为终止标记，通过辅助函数传递这个标记，就能完美解决没有NULL终止的问题。

内容的提问来源于stack exchange，提问作者David