Given a singly linked list and a key, count number of occurrences of given key in linked list. For example, if given linked list is 1->2->1->2->1->3->1 and given key is 1, then output should be 4.
Algorithm:
1. Initialize count as zero.
2. Loop through each element of linked list:
a) If element data is equal to the passed number then
increment the count.
3. Return count.
C++ Programming:
[pastacode lang=”cpp” manual=”%2F%2F%20C%2FC%2B%2B%20program%20to%20count%20occurrences%20in%20a%20linked%20list%0A%23include%3Cstdio.h%3E%0A%23include%3Cstdlib.h%3E%0A%20%0A%2F*%20Link%20list%20node%20*%2F%0Astruct%20node%0A%7B%0A%20%20%20%20int%20data%3B%0A%20%20%20%20struct%20node*%20next%3B%0A%7D%3B%0A%20%0A%2F*%20Given%20a%20reference%20(pointer%20to%20pointer)%20to%20the%20head%0A%20%20of%20a%20list%20and%20an%20int%2C%20push%20a%20new%20node%20on%20the%20front%0A%20%20of%20the%20list.%20*%2F%0Avoid%20push(struct%20node**%20head_ref%2C%20int%20new_data)%0A%7B%0A%20%20%20%20%2F*%20allocate%20node%20*%2F%0A%20%20%20%20struct%20node*%20new_node%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20(struct%20node*)%20malloc(sizeof(struct%20node))%3B%0A%20%0A%20%20%20%20%2F*%20put%20in%20the%20data%20%20*%2F%0A%20%20%20%20new_node-%3Edata%20%20%3D%20new_data%3B%0A%20%0A%20%20%20%20%2F*%20link%20the%20old%20list%20off%20the%20new%20node%20*%2F%0A%20%20%20%20new_node-%3Enext%20%3D%20(*head_ref)%3B%0A%20%0A%20%20%20%20%2F*%20move%20the%20head%20to%20point%20to%20the%20new%20node%20*%2F%0A%20%20%20%20(*head_ref)%20%20%20%20%3D%20new_node%3B%0A%7D%0A%20%0A%2F*%20Counts%20the%20no.%20of%20occurences%20of%20a%20node%0A%20%20%20(search_for)%20in%20a%20linked%20list%20(head)*%2F%0Aint%20count(struct%20node*%20head%2C%20int%20search_for)%0A%7B%0A%20%20%20%20struct%20node*%20current%20%3D%20head%3B%0A%20%20%20%20int%20count%20%3D%200%3B%0A%20%20%20%20while%20(current%20!%3D%20NULL)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(current-%3Edata%20%3D%3D%20search_for)%0A%20%20%20%20%20%20%20%20%20%20%20count%2B%2B%3B%0A%20%20%20%20%20%20%20%20current%20%3D%20current-%3Enext%3B%0A%20%20%20%20%7D%0A%20%20%20%20return%20count%3B%0A%7D%0A%20%0A%2F*%20Drier%20program%20to%20test%20count%20function*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Start%20with%20the%20empty%20list%20*%2F%0A%20%20%20%20struct%20node*%20head%20%3D%20NULL%3B%0A%20%0A%20%20%20%20%2F*%20Use%20push()%20to%20construct%20below%20list%0A%20%20%20%20%201-%3E2-%3E1-%3E3-%3E1%20%20*%2F%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%20%20%20push(%26head%2C%203)%3B%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%20%20%20push(%26head%2C%202)%3B%0A%20%20%20%20push(%26head%2C%201)%3B%0A%20%0A%20%20%20%20%2F*%20Check%20the%20count%20function%20*%2F%0A%20%20%20%20printf(%22count%20of%201%20is%20%25d%22%2C%20count(head%2C%201))%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”” highlight=”” provider=”manual”/]Output:
count of 1 is 3
Time Complexity: O(n)
Auxiliary Space: O(1)