Given a linked list and the task is to find the mode of the linked list.
Note: Mode is the value that appears most frequently in the Linked list.
Examples:
Input: List: 1 -> 2 -> 3 -> 2 -> 4 -> 3 -> 2 -> 5 -> 2
Output: 2
Explanation: 2 is the value that appears most frequently in the given Linked list.Input: List: 2 -> 1 -> 1 -> 6 -> 3 -> 2 -> 1
Output: 1
Explanation: 1 is the value that appears most frequently in the given Linked list.
Approach: To solve the problem follow the below idea:
- The idea is to create an unordered_map to store the frequency of each element in the linked list and traverse the linked list and update the frequency of each element in the unordered_map. Now keep track of the maximum frequency seen so far.
- In the second traversal, we find the element with the maximum frequency. We traverse the linked list again and check the frequency of each element. If the frequency of the element is equal to the maximum frequency seen so far, we set the mode to be that element.
Below are the steps for the above approach:
- Initialize an unordered map to keep track of the frequency of each element in the list.
- Initialize a variable max_freq = 0, to keep track of the maximum frequency of any element in the list.
- Initialize a pointer curr = head of the linked list.
- Traverse the linked list until curr becomes NULL. In each iteration,
- Increment the frequency of each element in the map, and update max_freq if the frequency of the current element is greater than max_freq.
- Again, traverse the linked list and check if the frequency of the current element is equal to max_freq, update the mode variable as the value of the current node.
- Return the value of mod.
Below is the code for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; struct Node { int data; Node* next; Node(int value) : data(value), next(nullptr) { } }; // Function to find Mode of linked list int findMode(Node* head) { unordered_map<int, int> freq; int max_freq = 0; Node* curr = head; // Count frequency of each element // in linked list while (curr != NULL) { freq[curr->data]++; max_freq = max(max_freq, freq[curr->data]); curr = curr->next; } // Find mode of linked list curr = head; int mode = 0; while (curr != NULL) { if (freq[curr->data] == max_freq) { mode = curr->data; break; } curr = curr->next; } return mode; } // Drivers code int main() { Node* head = new Node(1); head->next = new Node(2); head->next->next = new Node(3); head->next->next->next = new Node(2); head->next->next->next->next = new Node(4); head->next->next->next->next->next = new Node(3); head->next->next->next->next->next->next = new Node(2); head->next->next->next->next->next->next->next = new Node(5); head->next->next->next->next->next->next->next->next = nullptr; // Function Call int mode = findMode(head); cout << "Mode: " << mode << endl; return 0; } |
Java
import java.util.HashMap; import java.util.Map; public class Main { static class Node { int data; Node next; Node(int value) { data = value; next = null; } } static int findMode(Node head) { Map<Integer, Integer> freq = new HashMap<>(); int maxFreq = 0; Node curr = head; // Count frequency of each element in linked list while (curr != null) { freq.put(curr.data, freq.getOrDefault(curr.data, 0) + 1); maxFreq = Math.max(maxFreq, freq.get(curr.data)); curr = curr.next; } // Find mode of linked list curr = head; int mode = 0; while (curr != null) { if (freq.get(curr.data) == maxFreq) { mode = curr.data; break; } curr = curr.next; } return mode; } public static void main(String[] args) { Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(2); head.next.next.next.next = new Node(4); head.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next = new Node(2); head.next.next.next.next.next.next.next = new Node(5); head.next.next.next.next.next.next.next.next = null; int mode = findMode(head); System.out.println("Mode: " + mode); // should output "Mode: 2" } } |
Python3
class Node: def __init__(self, value): self.data = value self.next = None def findMode(head): freq = {} max_freq = 0 curr = head # Count frequency of each element in linked list while curr != None: freq[curr.data] = freq.get(curr.data, 0) + 1 max_freq = max(max_freq, freq[curr.data]) curr = curr.next # Find mode of linked list curr = head mode = 0 while curr != None: if freq[curr.data] == max_freq: mode = curr.data break curr = curr.next return mode if __name__ == "__main__": head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(2) head.next.next.next.next = Node(4) head.next.next.next.next.next = Node(3) head.next.next.next.next.next.next = Node(2) head.next.next.next.next.next.next.next = Node(5) head.next.next.next.next.next.next.next.next = None mode = findMode(head) print(f"Mode: {mode}") # output "Mode: 2" |
Javascript
class Node { constructor(value) { this.data = value; this.next = null; } } function findMode(head) { let freq = new Map(); let max_freq = 0; let curr = head; // Count frequency of each element in linked list while (curr != null) { freq.set(curr.data, (freq.get(curr.data) || 0) + 1); max_freq = Math.max(max_freq, freq.get(curr.data)); curr = curr.next; } // Find mode of linked list curr = head; let mode = 0; while (curr != null) { if (freq.get(curr.data) == max_freq) { mode = curr.data; break; } curr = curr.next; } return mode; } let head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(2); head.next.next.next.next = new Node(4); head.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next = new Node(2); head.next.next.next.next.next.next.next = new Node(5); head.next.next.next.next.next.next.next.next = null; let mode = findMode(head); console.log("Mode: " + mode); // output "Mode: 2" |
C#
using System; using System.Collections.Generic; public class Node { public int data; public Node next; public Node(int value) { data = value; next = null; } } public class Program { public static int FindMode(Node head) { Dictionary<int, int> freq = new Dictionary<int, int>(); int max_freq = 0; Node curr = head; // Count frequency of each element in linked list while (curr != null) { if (!freq.ContainsKey(curr.data)) { freq.Add(curr.data, 0); } freq[curr.data]++; max_freq = Math.Max(max_freq, freq[curr.data]); curr = curr.next; } // Find mode of linked list curr = head; int mode = 0; while (curr != null) { if (freq[curr.data] == max_freq) { mode = curr.data; break; } curr = curr.next; } return mode; } public static void Main() { Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(2); head.next.next.next.next = new Node(4); head.next.next.next.next.next = new Node(3); head.next.next.next.next.next.next = new Node(2); head.next.next.next.next.next.next.next = new Node(5); head.next.next.next.next.next.next.next.next = null; int mode = FindMode(head); Console.WriteLine("Mode: " + mode); // output "Mode: 2" } } |
Output
Mode: 2
Time Complexity: O(N)
Auxiliary Space: O(N)
Related Articles:
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
