Home > Article > Backend Development > 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.
Assume we have been given a list of character links
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.
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 -
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.
#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), where N is the size of the linked list.
Space complexity: O(1)
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.
#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), where N is the size of the linked list.
Space complexity: O(N), where N is the size of the linked list.
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!