So I have to count the nodes in a Circular Linked List recursively. I have a header that I am required to use:
int Recursive(node *head);
Is it possible to count the nodes in this list with only one pointer? What would the algorithm be for that?
int count(node* head)
{
if(head == nullptr)
return 0;
return countRecursive(head, head->next);
}
int countRecursive(node* head, node* current)
{
if(current == head) // our end condition!
return 1;
return 1 + countRecursive(head, current->next);
}
Basically we go in a circle and stop when we return to the head, adding 1 while
we go.