用一个参数计算循环链表中的节点？

Question

所以我必须递归地计算循环链表中的节点。我有一个 header 需要使用：

int Recursive(node *head);

是否可以只用一个指针来统计这个列表中的节点？算法是什么？

Answer 1

       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.

Answer 2

您可以分离一个节点以使其成为一个较小的列表，递归地计算该列表中的节点，然后重新附加附加节点。给你：

int count(Node* head) {
  // Base cases: (empty list and 1 node)
  if (!head) return 0;
  if (head->next == head) return 1;
  // Keep a pointer to the node to be removed
  Node* temp = head->next;
  // Remove the node
  head->next = temp->next;
  // Get the length of the new list
  int result = 1 + count(head);
  // Reconnect the node
  head->next = temp;
  return result;
}

用一个参数计算循环链表中的节点？

Counting Nodes in Circular Linked List with One Parameter?

c++

circular-list