Find the element in a linked list with frequency at least N / 3 | Java 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
class GFG { static class node { String i ; node next = null ; } ; static node newnode ( String s ) { node temp = new node ( ) ; temp . i = s ; temp . next = null ; return temp ; } static String Majority_in_linklist ( node head ) { String s = " " ; String t = " " ; int p = 0 , q = 0 ; node ptr = null ; while ( head != null ) { if ( s . equals ( head . i ) ) { p = p + 1 ; } else { if ( t . equals ( head . i ) ) { 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 . equals ( head . i ) ) { p = 1 ; } else { if ( t . equals ( head . i ) ) { q = 1 ; } } head = head . next ; } if ( p > q ) { return s ; } else { return t ; } } public static void main ( String [ ] arg ) { 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 " ) ; System . out . println ( Majority_in_linklist ( head ) ) ; } }