You are given a linked list. You have to write a function that will give frequency of a given number in linked list.
Here is a solution
Algorithm:
1. Initialize count as zero.
2. Loop through each element of linked list:
3. If element data is equal to the given number then increment the count.
4. Return count
#include<stdio.h> #include<stdlib.h> /* Link list node */ struct node { int data; struct node* next; }; void insert(struct node** head, int value) { struct node* new_node = (struct node*) malloc(sizeof(struct node)); new_node->data = value; new_node->next = (*head); (*head) = new_node; } /* Counts the no. of occurences of a node in a linked list */ int count(struct node* start, int item) { struct node* current = start; int count = 0; while (current != NULL) { if (current->data == item) count++; current = current->next; } return count; } // main program int main() { struct node* start = NULL; insert(&start, 2); insert(&start, 5); insert(&start, 1); insert(&start, 2); insert(&start, 2); /* Check the count function */ printf("count of 2 is %d", count(start, 2)); return 0; }
Complexity: O(N)
recursive:-
public class LinkedList {
static int k=0;
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
Node n6 = new Node(5);
Node n7 = new Node(7);
n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(n7);
int count = countNum(n1,5);
System.out.println(count);
}
private static int countNum(Node n1, int i) {
Node temp = n1;
if(temp==null)
{
return k;
}
if(temp.getData()==i)
{
k++;
}
return countNum(n1.getNext(),i);
}
}