链表中出现次数最多的字符

---

给定一个字符的单链表，我们的任务是打印在链表中出现次数最多的字符。如果多个字符具有相同的出现次数，则打印最后出现的字符。

单链表是一种线性数据结构，由节点组成。每个节点包含数据和指向下一个节点的指针，该指针包含下一个节点的内存地址，因为分配给每个节点的内存不是连续的。

示例

假设我们给定一个字符的链表，如下所示

示例 1

输入：LL = a -> b -> c -> c -> c

输出：出现次数最多的字符是 c。

解释：在给定的链表 LL 中，a 出现 1 次，b 出现 1 次，c 出现 3 次。因此，输出为 c。

示例 2

输入

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

输出：出现次数最多的字符是 z。

解释：在给定的链表 LL 中，x 出现 2 次，y 出现 2 次，z 出现 2 次。所有字符的出现次数都相同，因为 z 最后出现，因此输出为 z。

我们将讨论两种方法。让我们在下面的部分中查看它们 -

方法 1：迭代计数频率

此方法的思路是，我们将遍历链表并统计每个字符的频率，然后找出频率最高的字符，如果多个字符具有相同的频率，则打印该字符，如果多个字符具有相同的频率，则返回最后一个字符。

示例

#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;
}

输出

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

时间复杂度

:O(N*N)，其中 N 是链表的大小。

空间复杂度：O(1)

方法 2：使用计数数组

此方法的思路是，我们将维护一个计数数组，在其中存储每个字符的频率，然后遍历该数组并找到频率最高的字符。打印该字符，如果多个字符具有相同的频率，则返回最后一个字符。

示例

#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;
}

输出

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

时间复杂度

O(N)，其中 N 是链表的大小。

空间复杂度：O(N)，其中 N 是链表的大小。

结论

在这里，我们讨论了如何在链表中找到出现次数最多的字符。为了找到出现次数最多的字符，我们讨论了两种方法。第一种方法使用 while 循环遍历给定链表的每个字符，第二种方法使用 for 循环遍历每个小写字符并维护计数。