Majority element in a linked list

0 0 11 minutes read

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>

Output

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>

Output

majority element is 1

Time Complexity: O(n)
Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!