Find the element in a linked list with frequency at least N / 3 | C ++ program to find an element with frequency of at least N / 3 in a linked list ; Structure of a node for the linked list ; Utility function to create a node ; Function to find and return the element with frequency of at least N / 3 ; Candidates for being the required majority element ; Store the frequencies of the respective candidates ; Iterate all nodes ; Increase frequency of candidate s ; Increase frequency of candidate t ; Set the new sting as candidate for majority ; Set the new sting as second candidate for majority ; Decrease the frequency ; Check the frequency of two final selected candidate linklist ; Increase the frequency of first candidate ; Increase the frequency of second candidate ; Return the string with higher frequency ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct node { string i ; node * next = NULL ; } ; struct node * newnode ( string s ) { struct node * temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ; temp -> i = s ; temp -> next = NULL ; return temp ; } string Majority_in_linklist ( node * head ) { string s = " " , t = " " ; int p = 0 , q = 0 ; node * ptr = NULL ; while ( head != NULL ) { if ( s . compare ( head -> i ) == 0 ) { p = p + 1 ; } else { if ( t . compare ( head -> i ) == 0 ) { q = q + 1 ; } else { if ( p == 0 ) { s = head -> i ; p = 1 ; } else { if ( q == 0 ) { t = head -> i ; q = 1 ; } else { p = p - 1 ; q = q - 1 ; } } } } head = head -> next ; } head = ptr ; p = 0 ; q = 0 ; while ( head != NULL ) { if ( s . compare ( head -> i ) == 0 ) { p = 1 ; } else { if ( t . compare ( head -> i ) == 0 ) { q = 1 ; } } head = head -> next ; } if ( p > q ) { return s ; } else { return t ; } } int main ( ) { node * ptr = NULL ; node * head = newnode ( " geeks " ) ; head -> next = newnode ( " geeks " ) ; head -> next -> next = newnode ( " abcd " ) ; head -> next -> next -> next = newnode ( " game " ) ; head -> next -> next -> next -> next = newnode ( " game " ) ; head -> next -> next -> next -> next -> next = newnode ( " knight " ) ; head -> next -> next -> next -> next -> next -> next = newnode ( " harry " ) ; head -> next -> next -> next -> next -> next -> next -> next = newnode ( " geeks " ) ; cout << Majority_in_linklist ( head ) << endl ; return 0 ; }