Find the element in a linked list with frequency at least N / 3 | 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 node { constructor ( ) { this . i = " " ; this . next = null ; } } function newnode ( s ) { var temp = new node ( ) ; temp . i = s ; temp . next = null ; return temp ; } function Majority_in_linklist ( head ) { var s = " " ; var t = " " ; var p = 0 , q = 0 ; var ptr = null ; while ( head != null ) { if ( s == head . i ) { p = p + 1 ; } else { if ( t == 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 == head . i ) { p = 1 ; } else { if ( t == head . i ) { q = 1 ; } } head = head . next ; } if ( p > q ) { return s ; } else { return t ; } } var head = newnode ( " " ) ; head . next = newnode ( " " ) ; head . next . next = newnode ( " " ) ; head . next . next . next = newnode ( " " ) ; head . next . next . next . next = newnode ( " " ) ; head . next . next . next . next . next = newnode ( " " ) ; head . next . next . next . next . next . next = newnode ( " " ) ; head . next . next . next . next . next . next . next = newnode ( " " ) ; document . write ( Majority_in_linklist ( head ) ) ;