Count Occurrences of an Integer in a Linked List in C++

In this problem, we are given a linked list. Our task is to create a function that will be able to count the number of times a given number occurs in the linked list.

Let’s take an example to understand the problem,

Input

Linked list = 10-> 50 -> 10 -> 20 -> 100 -> 10, int = 10

Output

3

Explaination − the number 10 occurs 3 times in the linked list.

The solution to this problem is simple, just traverse the linked list and increment a counter the current node value is equal to the given number.

The looping over the nodes of the linked list can be done by using iteration as well as recursion and we are illustrating both methods to solve the problem

Program to illustrate the solution using iteration,

Example

 Live Demo

#include <iostream>
using namespace std;
class Node {
   public:
   int data;
   Node* next;
};
void push(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
int countInt(Node* head, int search_for) {
   Node* current = head;
   int intCount = 0;
   while (current != NULL) {
      if (current->data == search_for)
         intCount++;
      current = current->next;
   }
   return intCount;
}
int main() {
   Node* head = NULL;
   push(&head, 10);
   push(&head, 40);
   push(&head, 10);
   push(&head, 50);
   push(&head, 20);
   push(&head, 90);
   push(&head, 10);
   cout<<"The count of 10 in the linked list is "<<countInt(head, 10);
   return 0;
}

Output

The count of 10 in the linked list is 3

Program to illustrate the solution using recurssion,

Example

 Live Demo

#include <iostream>
using namespace std;
int intCount = 0;
class Node {
   public:
   int data;
   Node* next;
};
void push(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
int countInt(struct Node* head, int key){
   if (head == NULL)
   return intCount;
   if (head->data == key)
   intCount++;
   return countInt(head->next, key);
}
int main() {
   Node* head = NULL;
   push(&head, 10);
   push(&head, 40);
   push(&head, 10);
   push(&head, 50);
   push(&head, 20);
   push(&head, 90);
   push(&head, 10);
   cout<<"The count of 10 in the linked list is "<<countInt(head, 10);
   return 0;
}

Output

The count of 10 in the linked list is 3