The character that appears most often in the linked list

We are given a singly linked list of characters, and our task is to print the character that appears most often in the linked list. If multiple characters occur the same number of times, the last occurrence of the character is printed.

Singly linked list is a linear data structure composed of nodes. Each node contains data and a pointer to the next node, which contains the memory address of the next node because the memory allocated to each node is not contiguous.

Example

Assume we have been given a list of character links

Example 1

Input: LL = a -> b -> c -> c -> c

Output: The most common character is c.

Explanation: In the given linked list LL, a appears once, b appears once, and c appears 3 times. Therefore, the output is c.

Example 2

enter:

LL = x -> x -> y -> y -> z -> z

Output: The largest occurring character is z.

Explanation: In the given linked list LL, x appears 2 times, y appears 2 times, and z appears 2 times. All occurrences are the same because z appears last, so the output is z.

Here we will discuss two methods. Let’s look at the following parts -

Method 1: Iterative calculation frequency

The idea of ​​this method is that we will traverse the linked list and calculate the frequency of each character, then find the character with the highest frequency, and if multiple characters have the same frequency, print the character and return the last character.

Example

#include <iostream>
using namespace std;
// creating a class to have a structure for linked list nodes 
class Node{
   public:
   char data; // variable to store the characters
   Node* next = NULL; // variable to store the address of the next node     
   Node(char cur){
      data = cur;
   }
};
// function to print the elements of the linked list 
void printLL(Node* head){   
   // creating a temporary pointer 
   Node* temp = head;    
   while(temp != nullptr){
      cout<<temp->data<<" -> ";
      temp = temp->next;
   }
   cout<<"NULL"<<endl;
}
// function to find the max frequency 
void maxFreq(Node* head){
   // traversing over the linked list for each character 
   // starting from the first character to the last character     
   int ans = 0; // variable to store the maximum frequency 
   char char_ans;
   Node* temp_first = head; // variable to store the current first node     
   while(temp_first != nullptr){
      int cur = 0; // variable to store the frequency of the current character 
      Node* temp = temp_first;        
      while(temp != nullptr){
         if(temp->data == temp_first->data){
            cur++;
         }
         temp = temp->next;
      }
      if(ans < cur){
         ans = cur;
         char_ans = temp_first->data;
      }
      temp_first = temp_first->next;
   }
   cout<<"The last character in the given linked list is '"<<char_ans<<"' with the frequency of "<< ans<<endl;
}
// main function 
int main(){
   // defining the linked list 
   Node* head = new Node('a');
   head->next = new Node('b');
   head->next->next = new Node('b');
   head->next->next->next = new Node('c');
   head->next->next->next->next = new Node('d');
   head->next->next->next->next->next = new Node('d');
   head->next->next->next->next->next->next = new Node('d');  
   cout<<"The given linked list is: "<<endl;
   printLL(head);   
   maxFreq(head);
   return 0;
}

Output

The given linked list is: 
a -> b -> b -> c -> d -> d -> d -> NULL
The last character in the given linked list is 'd' with the frequency of 3

Time complexity

: O(N*N), where N is the size of the linked list.

Space complexity: O(1)

Method 2: Use counting array

The idea of ​​this approach is that we will maintain an array of counts where we store the frequency of each character and then iterate through the array and find the highest frequency character. If multiple characters have the same frequency, print that character and then return the last character.

Example

#include <iostream>
using namespace std;
// creating a class to have a structure for linked list nodes 
class Node{
   public:
   char data; // variable to store the characters
   Node* next = NULL; // variable to store the address of the next node     
   Node(char cur){
      data = cur;
   }
};
// function to print the elements of the linked list 
void printLL(Node* head){    
   // creating a temporary pointer 
   Node* temp = head;    
   while(temp != nullptr){
      cout<<temp->data<<" -> ";
      temp = temp->next;
   }
   cout<<"NULL"<<endl;
}
// function to find the max frequency 
void maxFreq(Node* head){
   int ans = 0; // variable to store the maximum frequency 
   char char_ans;    
   // traversing over the linked list for each lowercase character 
   for(char i = 'a'; i<= 'z'; i++){
      Node* temp = head;
      int cur = 0; // variable to store the frequency of the current character 
      while(temp != nullptr){
         if(temp->data == i){
            cur++;
         }
         temp = temp->next;
      }
      if(ans <= cur){
         ans = cur;
         char_ans = i;
      }
   }     
   cout<<"The last character in the given linked list is '"<<char_ans<<"' with the frequency of "<< ans<<endl;
}
int main(){
   // defining the linked list 
   Node* head = new Node('a');
   head->next = new Node('b');
   head->next->next = new Node('b');
   head->next->next->next = new Node('c');
   head->next->next->next->next = new Node('e');
   head->next->next->next->next->next = new Node('d');
   head->next->next->next->next->next->next = new Node('d');  
   cout<<"The given linked list is: "<<endl;
   printLL(head);   
   maxFreq(head);
   return 0;
}

Output

The given linked list is: 
a -> b -> b -> c -> e -> d -> d -> NULL
The last character in the given linked list is 'd' with the frequency of 2

Time complexity

O(N), where N is the size of the linked list.

Space complexity: O(N), where N is the size of the linked list.

in conclusion

Here we discuss how to find the characters that appear most in the linked list. To find the maximum occurrence of characters, we discussed two methods. The first method uses a while loop for each character of the given linked list and the second method uses a for loop for each lower case character and maintains the count.

The above is the detailed content of The character that appears most often in the linked list. For more information, please follow other related articles on the PHP Chinese website!