Given a linked list, find majority element. An element is called Majority element if it appears more than or equal to n/2 times where n is total number of nodes in the linked list.
Examples:
Input : 1->2->3->4->5->1->1->1->NULL Output : 1 Explanation 1 occurs 4 times Input :10->23->11->9->54->NULL Output :NO majority element
Method 1(simple): Run two loops starting from head and count frequency of each element iteratively. Print the element whose frequency is greater than or equal to n/2. In this approach time complexity will be O(n*n) where n is the number of nodes in the linked list.
Implementation:
C++
// C++ program to find majority element in // a linked list #include <bits/stdc++.h> using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to get the nth node from the last of a linked list*/ int majority( struct Node* head) { struct Node* p = head; int total_count = 0, max_count = 0, res = -1; while (p != NULL) { // Count all occurrences of p->data int count = 1; struct Node* q = p->next; while (q != NULL) { if (p->data == q->data) count++; q = q->next; } // Update max_count and res if count // is more than max_count if (count > max_count) { max_count = count; res = p->data; } p = p->next; total_count++; } if (max_count >= total_count/2) return res; // if we reach here it means no // majority element is present. // and we assume that all the // element are positive return -1; } void push( struct Node** head_ref, int new_data) { struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Driver program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; // create linked push(&head, 1); push(&head, 1); push(&head, 1); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); int res = majority(head); if (res != (-1)) cout << "Majority element is " << res; else cout << "No majority element" ; return 0; } |
Java
// Java program to find majority element in // a linked list import java.util.*; class GFG { static Node head; /* Link list node */ static class Node { int data; Node next; }; /* Function to get the nth node from the last of a linked list*/ static int majority(Node head) { Node p = head; int total_count = 0 , max_count = 0 , res = - 1 ; while (p != null ) { // Count all occurrences of p->data int count = 1 ; Node q = p.next; while (q != null ) { if (p.data == q.data) count++; q = q.next; } // Update max_count and res if count // is more than max_count if (count > max_count) { max_count = count; res = p.data; } p = p.next; total_count++; } if (max_count >= total_count / 2 ) return res; // if we reach here it means no // majority element is present. // and we assume that all the // element are positive return - 1 ; } static void push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref; } // Driver Code public static void main(String[] args) { /* Start with the empty list */ head = null ; // create linked push(head, 1 ); push(head, 1 ); push(head, 1 ); push(head, 5 ); push(head, 4 ); push(head, 3 ); push(head, 2 ); push(head, 1 ); int res = majority(head); if (res != (- 1 )) System.out.println( "Majority element is " + res); else System.out.println( "No majority element" ); } } // This code is contributed by Princi Singh |
Python3
# Python3 program to find majority element in # a linked list head = None # Link list node class Node : def __init__( self ): self .data = 0 self . next = None # Function to get the nth node from # the last of a linked list def majority(head): p = head total_count = 0 max_count = 0 res = - 1 while (p ! = None ): # Count all occurrences of p->data count = 1 q = p. next while (q ! = None ): if (p.data = = q.data): count = count + 1 q = q. next # Update max_count and res if count # is more than max_count if (count > max_count): max_count = count res = p.data p = p. next total_count = total_count + 1 if (max_count > = total_count / 2 ): return res # if we reach here it means no # majority element is present. # and we assume that all the # element are positive return - 1 def push( head_ref, new_data): global head new_node = Node() new_node.data = new_data new_node. next = head_ref head_ref = new_node head = head_ref # Driver Code # Start with the empty list head = None # create linked push(head, 1 ) push(head, 1 ) push(head, 1 ) push(head, 5 ) push(head, 4 ) push(head, 3 ) push(head, 2 ) push(head, 1 ) res = majority(head) if (res ! = ( - 1 )): print ( "Majority element is " , res) else : print ( "No majority element" ) # This code is contributed by Arnab Kundu |
C#
// C# program to find majority element in // a linked list using System; class GFG { static Node head; /* Link list node */ public class Node { public int data; public Node next; }; /* Function to get the nth node from the last of a linked list*/ static int majority(Node head) { Node p = head; int total_count = 0, max_count = 0, res = -1; while (p != null ) { // Count all occurrences of p->data int count = 1; Node q = p.next; while (q != null ) { if (p.data == q.data) count++; q = q.next; } // Update max_count and res if count // is more than max_count if (count > max_count) { max_count = count; res = p.data; } p = p.next; total_count++; } if (max_count >= total_count / 2) return res; // if we reach here it means no // majority element is present. // and we assume that all the // element are positive return -1; } static void push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref; } // Driver Code public static void Main(String[] args) { /* Start with the empty list */ head = null ; // create linked push(head, 1); push(head, 1); push(head, 1); push(head, 5); push(head, 4); push(head, 3); push(head, 2); push(head, 1); int res = majority(head); if (res != (-1)) Console.WriteLine( "Majority element is " + res); else Console.WriteLine( "No majority element" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program to find majority element in // a linked list var head = null ; /* Link list node */ class Node { constructor() { this .data = 0; this .next = null ; } }; /* Function to get the nth node from the last of a linked list*/ function majority(head) { var p = head; var total_count = 0, max_count = 0, res = -1; while (p != null ) { // Count all occurrences of p->data var count = 1; var q = p.next; while (q != null ) { if (p.data == q.data) count++; q = q.next; } // Update max_count and res if count // is more than max_count if (count > max_count) { max_count = count; res = p.data; } p = p.next; total_count++; } if (max_count >= total_count / 2) return res; // if we reach here it means no // majority element is present. // and we assume that all the // element are positive return -1; } function push(head_ref, new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; head = head_ref; } // Driver Code /* Start with the empty list */ head = null ; // create linked push(head, 1); push(head, 1); push(head, 1); push(head, 5); push(head, 4); push(head, 3); push(head, 2); push(head, 1); var res = majority(head); if (res != (-1)) document.write( "Majority element is " + res); else document.write( "No majority element" ); </script> |
Majority element is 1
Time Complexity: O(n*n)
Auxiliary Space: O(1)
Method 2: Use hashing technique. We count frequency of each element and then we print the element whose frequency is ? n/2;
Implementation:
C++
// CPP program to find majority element // in the linked list using hashing #include <bits/stdc++.h> using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; /* Function to get the nth node from the last of a linked list*/ int majority( struct Node* head) { struct Node* p = head; // Storing elements and their frequencies // in a hash table. unordered_map< int , int > hash; int total_count = 0; while (p != NULL) { // increase every element // frequency by 1 hash[p->data]++; p = p->next; total_count++; } // Check if frequency of any element // is more than or equal to total_count/2 for ( auto x : hash) if (x.second >= total_count/2) return x.first; // If we reach here means no majority element // is present. We assume that all the element // are positive return -1; } void push( struct Node** head_ref, int new_data) { struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } // Driver program to test above function int main() { /* Start with the empty list */ struct Node* head = NULL; push(&head, 1); push(&head, 1); push(&head, 1); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); int res = majority(head); if (res != (-1)) cout << "majority element is " << res; else cout << "NO majority element" ; return 0; } |
Java
// JAVA program to find majority element // in the linked list using hashing import java.util.*; class GFG { /* Link list node */ static class Node { int data; Node next; }; /* Function to get the nth node from the last of a linked list*/ static int majority(Node head) { Node p = head; // Storing elements and their frequencies // in a hash table. HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>(); int total_count = 0 ; while (p != null ) { // increase every element // frequency by 1 if (hash.containsKey(p.data)) hash.put(p.data, hash.get(p.data) + 1 ); else hash.put(p.data, 1 ); p = p.next; total_count++; } // Check if frequency of any element // is more than or equal to total_count/2 for (Map.Entry<Integer,Integer> x : hash.entrySet()) if (x.getValue() >= total_count/ 2 ) return x.getKey(); // If we reach here means no majority element // is present. We assume that all the element // are positive return - 1 ; } static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref; } // Driver code public static void main(String[] args) { /* Start with the empty list */ Node head = null ; head = push(head, 1 ); head = push(head, 1 ); head = push(head, 1 ); head = push(head, 5 ); head = push(head, 4 ); head = push(head, 3 ); head = push(head, 2 ); head = push(head, 1 ); int res = majority(head); if (res != (- 1 )) System.out.print( "majority element is " + res); else System.out.print( "NO majority element" ); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to find majority element # in the linked list using hashing ''' Link list node ''' class Node: def __init__( self , data): self .data = data self . next = None ''' Function to get the nth node from the last of a linked list''' def majority(head): p = head; # Storing elements and their frequencies # in a hash table. hash = dict () total_count = 0 ; while (p ! = None ): # increase every element # frequency by 1 if p.data not in hash : hash [p.data] = 0 hash [p.data] + = 1 p = p. next ; total_count + = 1 # Check if frequency of any element # is more than or equal to total_count/2 for x in hash .keys(): if ( hash [x] > = total_count / / 2 ): return x; # If we reach here means no majority element # is present. We assume that all the element # are positive return - 1 ; def push(head_ref, new_data): new_node = Node(new_data) new_node. next = (head_ref); (head_ref) = new_node; return head_ref # Driver code if __name__ = = '__main__' : ''' Start with the empty list ''' head = None head = push(head, 1 ); head = push(head, 1 ); head = push(head, 1 ); head = push(head, 5 ); head = push(head, 4 ); head = push(head, 3 ); head = push(head, 2 ); head = push(head, 1 ); res = majority(head); if (res ! = ( - 1 )): print ( "majority element is " + str (res)) else : print ( "NO majority element" ) # This code is contributed by rutvik_56 |
C#
// C# program to find majority element // in the linked list using hashing using System; using System.Collections.Generic; class GFG { /* Link list node */ public class Node { public int data; public Node next; }; /* Function to get the nth node from the last of a linked list*/ static int majority(Node head) { Node p = head; // Storing elements and their frequencies // in a hash table. Dictionary< int , int > hash = new Dictionary< int , int >(); int total_count = 0; while (p != null ) { // increase every element // frequency by 1 if (hash.ContainsKey(p.data)) hash[p.data] = hash[p.data] + 1; else hash.Add(p.data, 1); p = p.next; total_count++; } // Check if frequency of any element // is more than or equal to total_count/2 foreach (KeyValuePair< int , int > x in hash) if (x.Value >= total_count/2) return x.Key; // If we reach here means no majority element // is present. We assume that all the element // are positive return -1; } static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref; } // Driver code public static void Main(String[] args) { /* Start with the empty list */ Node head = null ; head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); int res = majority(head); if (res != (-1)) Console.Write( "majority element is " + res); else Console.Write( "NO majority element" ); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to find majority element // in the linked list using hashing /* Link list node */ class Node { constructor() { this .data = 0; this .next = null ; } } /* Function to get the nth node from the last of a linked list*/ function majority(head) { var p = head; // Storing elements and their frequencies // in a hash table. var hash = {}; var total_count = 0; while (p != null ) { // increase every element // frequency by 1 if (hash.hasOwnProperty(p.data)) hash[p.data] = hash[p.data] + 1; else hash[p.data] = 1; p = p.next; total_count++; } // Check if frequency of any element // is more than or equal to total_count/2 for (const [key, value] of Object.entries(hash)) { if (value >= parseInt(total_count / 2)) return key; // If we reach here means no majority element // is present. We assume that all the element // are positive return -1; } } function push(head_ref, new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref; } // Driver code /* Start with the empty list */ var head = null ; head = push(head, 1); head = push(head, 1); head = push(head, 1); head = push(head, 5); head = push(head, 4); head = push(head, 3); head = push(head, 2); head = push(head, 1); var res = majority(head); if (res != -1) document.write( "majority element is " + res); else document.write( "NO majority element" ); // This code is contributed by rdtank. </script> |
majority element is 1
Time Complexity: O(n)
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!