Maximum occurring character in a linked list
Last Updated :
03 Aug, 2022
Given a linked list of characters. The task is to find the maximum occurring character in the linked list. if there are multiple answers, return the first maximum occurring character.
Examples:
Input : g -> e -> e -> k -> s
Output : e
Input : a -> a -> b -> b -> c -> c -> d -> d
Output : d
Method 1: Iteratively count the frequency of each character in a string and return the one which has maximum occurrence.
Implementation:
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
char data;
struct Node *next;
};
char maxChar(struct Node *head) {
struct Node *p = head;
int max = -1;
char res;
while (p != NULL) {
struct Node *q = p->next;
int count = 1;
while (q != NULL) {
if (p->data == q->data)
count++;
q = q->next;
}
if (max < count) {
res = p->data;
max = count;
}
p = p->next;
}
return res;
}
void push(struct Node **head_ref, char new_data) {
struct Node *new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main() {
struct Node *head = NULL;
char str[] = "skeegforskeeg";
int i;
for (i = 0; str[i] != '\0'; i++)
push(&head, str[i]);
cout << maxChar(head);
return 0;
}
|
Java
import java.util.*;
class GFG{
static class Node
{
char data;
Node next;
};
static Node head_ref;
static char maxChar(Node head)
{
Node p = head;
int max = -1;
char res = '0';
while (p != null)
{
Node q = p.next;
int count = 1;
while (q != null)
{
if (p.data == q.data)
count++;
q = q.next;
}
if (max < count)
{
res = p.data;
max = count;
}
p = p.next;
}
return res;
}
static void push(char new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
}
public static void main(String[] args)
{
head_ref = null;
String str = "skeegforskeeg";
char st[] = str.toCharArray();
int i;
for (i = 0; i < st.length; i++)
push(st[i]);
System.out.print(maxChar(head_ref));
}
}
|
Python3
class Node:
def __init__(self, data):
self.data = data;
self.next = next;
head_ref = None;
def maxChar(head):
p = head;
max = -1;
res = '0';
while (p != None):
q = p.next;
count = 1;
while (q != None):
if (p.data == q.data):
count += 1;
q = q.next;
if (max < count):
res = p.data;
max = count;
p = p.next;
return res;
def push(new_data):
global head_ref;
new_node = Node(0);
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head_ref = new_node;
if __name__ == '__main__':
head_ref = None;
str = "skeegforskeeg";
st = str;
i = 0;
for i in range(len(st)):
push(st[i]);
print(maxChar(head_ref));
|
C#
using System;
class GFG
{
class Node
{
public char data;
public Node next;
};
static Node head_ref;
static char maxChar(Node head)
{
Node p = head;
int max = -1;
char res = '0';
while (p != null)
{
Node q = p.next;
int count = 1;
while (q != null)
{
if (p.data == q.data)
count++;
q = q.next;
}
if (max < count)
{
res = p.data;
max = count;
}
p = p.next;
}
return res;
}
static void push(char new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
}
public static void Main(string[] args)
{
head_ref = null;
string str = "skeegforskeeg";
char []st = str.ToCharArray();
int i;
for (i = 0; i < st.Length; i++)
push(st[i]);
Console.Write(maxChar(head_ref));
}
}
|
Javascript
<script>
class Node
{
constructor()
{
this.data = '';
this.next = null;
}
};
var head_ref = null;
function maxChar( head)
{
var p = head;
var max = -1;
var res = '0';
while (p != null)
{
var q = p.next;
var count = 1;
while (q != null)
{
if (p.data == q.data)
count++;
q = q.next;
}
if (max < count)
{
res = p.data;
max = count;
}
p = p.next;
}
return res;
}
function push(new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
}
head_ref = null;
var str = "skeegforskeeg";
var st = str.split('');
var i;
for (i = 0; i < st.length; i++)
push(st[i]);
document.write(maxChar(head_ref));
</script>
|
Time complexity: (N*N)
Method 2: (use count array)
Create a count array and count each character frequency return the maximum occurring character.
C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
char data;
struct Node *next;
};
char maxChar(struct Node *head) {
struct Node *p = head;
int hash[256] = {0};
while (p != NULL) {
hash[p->data]++;
p = p->next;
}
p = head;
int max = -1;
char res;
while (p != NULL) {
if (max < hash[p->data]) {
res = p->data;
max = hash[p->data];
}
p = p->next;
}
return res;
}
void push(struct Node **head_ref, char new_data) {
struct Node *new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main() {
struct Node *head = NULL;
char str[] = "skeegforskeeg";
for (int i = 0; str[i] != '\0'; i++)
push(&head, str[i]);
cout << maxChar(head);
return 0;
}
|
Java
import java.util.*;
class GFG
{
static class Node
{
char data;
Node next;
};
static Node head;
static char maxChar(Node head)
{
Node p = head;
int []hash = new int[256];
while (p != null)
{
hash[p.data]++;
p = p.next;
}
p = head;
int max = -1;
char res = 0;
while (p != null)
{
if (max < hash[p.data])
{
res = p.data;
max = hash[p.data];
}
p = p.next;
}
return res;
}
static void push(Node head_ref, char new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head = head_ref;
}
public static void main(String[] args)
{
head = null;
char str[] = "skeegforskeeg".toCharArray();
for (int i = 0; i < str.length; i++)
{
push(head, str[i]);
}
System.out.println(maxChar(head));
}
}
|
Python3
class Node:
def __init__(self):
self.data = ''
self.next = None
def maxChar(head):
p = head
hash = [0 for i in range(256)]
while (p != None):
hash[ord(p.data)] += 1
p = p.next
p = head
max = -1
res = ''
while (p != None):
if (max < hash[ord(p.data)]):
res = p.data
max = hash[ord(p.data)]
p = p.next
return res
def push(head_ref, new_data):
new_node = Node()
new_node.data = new_data
new_node.next = (head_ref)
(head_ref) = new_node
return head_ref
if __name__=='__main__':
head = None
str = "skeegforskeeg"
for i in range(len(str)):
head = push(head, str[i])
print(maxChar(head))
|
C#
using System;
public class GFG
{
class Node
{
public char data;
public Node next;
};
static Node head;
static char maxChar(Node head)
{
Node p = head;
int []hash = new int[256];
while (p != null)
{
hash[p.data]++;
p = p.next;
}
p = head;
int max = -1;
char res= '\x0000';
while (p != null)
{
if (max < hash[p.data])
{
res = p.data;
max = hash[p.data];
}
p = p.next;
}
return res;
}
static void push(Node head_ref, char new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head = head_ref;
}
public static void Main(String[] args)
{
head = null;
char []str = "skeegforskeeg".ToCharArray();
for (int i = 0; i < str.Length; i++)
{
push(head, str[i]);
}
Console.WriteLine(maxChar(head));
}
}
|
Javascript
<script>
class Node
{
constructor()
{
this.data = 0;
this.next = null;
}
}
var head = null;
function maxChar(head)
{
var p = head;
var hash = new Array(256).fill(0);
while (p != null)
{
hash[p.data.charCodeAt(0)]++;
p = p.next;
}
p = head;
var max = -1;
var res = "";
while (p != null)
{
if (max < hash[p.data.charCodeAt(0)])
{
res = p.data;
max = hash[p.data.charCodeAt(0)];
}
p = p.next;
}
return res;
}
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;
}
head = null;
var str = "skeegforskeeg".split("");
for(var i = 0; i < str.length; i++)
{
push(head, str[i]);
}
document.write(maxChar(head) + "<br>");
</script>
|
Time complexity: (N)