Search code examples
c++circular-list

Counting Nodes in Circular Linked List with One Parameter?


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?


Solution

  •        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.