C ++でリンクリストの長さ（反復および再帰）を検索

ここでは、反復的かつ再帰的なアプローチを使用して、リンクリストの長さを見つける方法を説明します。ヘッドポインタが指定されている場合は、次の手順に従って長さを取得する必要があります。

• 反復アプローチの場合-

  • リストの先頭を取り、現在のポインタがnullでなくなるまで、次のノードに移動してカウントを増やします。

• 再帰的アプローチの場合-

  • 引数としてheadを渡します。基本条件は、引数がnullの場合、0を返します。それ以外の場合は、再帰的にリストに入り、現在のノードから次のノードを送信し、1+サブリストの長さを返します

例

#include<iostream>
using namespace std;
class Node {
   public:
      int data;
   Node* next;
};
void append(struct Node** start, int data) {
   struct Node* new_node = new Node;
   new_node->data = data;
   new_node->next = (*start);
   (*start) = new_node;
}
int count_recursive(Node* start) {
   if (start == NULL)
      return 0;
   return 1 + count_recursive(start->next);
}
int count_iterative(Node* start) {
   int count = 0;
   Node* current = start;
   while (current != NULL) {
      count++;
      current = current->next;
   }
   return count;
}
int main() {
   Node* start = NULL;
   append(&start, 1);
   append(&start, 3);
   append(&start, 1);
   append(&start, 2);
   append(&start, 1);
   cout << "Node count using iterative approach: " << count_iterative(start) << endl;
   cout << "Node count using recursion: " << count_recursive(start);
}

出力

Node count using iterative approach: 5
Node count using recursion: 5