Find the element in a linked list with frequency at least N / 3 | Structure of a node for the linked list ; 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 : NEW_LINE INDENT def __init__ ( self , s ) : NEW_LINE INDENT self . i = s NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def Majority_in_linklist ( head ) : NEW_LINE INDENT s , t = " " , " " NEW_LINE p , q = 0 , 0 NEW_LINE ptr = None NEW_LINE while head != None : NEW_LINE INDENT if s == head . i : NEW_LINE INDENT p = p + 1 NEW_LINE DEDENT else : NEW_LINE INDENT if t == head . i : NEW_LINE INDENT q = q + 1 NEW_LINE DEDENT else : NEW_LINE INDENT if p == 0 : NEW_LINE INDENT s = head . i NEW_LINE p = 1 NEW_LINE DEDENT else : NEW_LINE INDENT if q == 0 : NEW_LINE INDENT t = head . i NEW_LINE q = 1 NEW_LINE DEDENT else : NEW_LINE INDENT p = p - 1 NEW_LINE q = q - 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT head = head . next NEW_LINE DEDENT head = ptr NEW_LINE p = 0 NEW_LINE q = 0 NEW_LINE while head != None : NEW_LINE INDENT if s == head . i : NEW_LINE INDENT p = 1 NEW_LINE DEDENT else : NEW_LINE INDENT if t == head . i : NEW_LINE INDENT q = 1 NEW_LINE DEDENT DEDENT head = head . next NEW_LINE DEDENT if p > q : NEW_LINE INDENT return s NEW_LINE DEDENT else : NEW_LINE INDENT return t NEW_LINE DEDENT DEDENT ptr = None NEW_LINE head = Node ( " geeks " ) NEW_LINE head . next = Node ( " geeks " ) NEW_LINE head . next . next = Node ( " abcd " ) NEW_LINE head . next . next . next = Node ( " game " ) NEW_LINE head . next . next . next . next = Node ( " game " ) NEW_LINE head . next . next . next . next . next = Node ( " knight " ) NEW_LINE head . next . next . next . next . next . next = Node ( " harry " ) NEW_LINE head . next . next . next . next . next . next . next = Node ( " geeks " ) NEW_LINE print ( Majority_in_linklist ( head ) ) NEW_LINE