Linked List Frequency

class Solution {
public:
    ListNode* elementFrequencies(ListNode* head) {
        unordered_map<int, ListNode*> freqMap;
        ListNode* currentNode = head;
        ListNode* freqHead = nullptr;
    
        while (currentNode != nullptr) {
            if (freqMap.find(currentNode->val) != freqMap.end()) {
                ListNode* nodeFreq = freqMap[currentNode->val];
                nodeFreq->val += 1;
            } else {
                ListNode* newNodeFreq = new ListNode(1, freqHead);
                freqMap[currentNode->val] = newNodeFreq;
                freqHead = newNodeFreq;
            }
            currentNode = currentNode->next;
        }
        return freqHead;
    }
};

In this solution, the goal is to calculate the frequency of each element in a linked list using a C++ program, and then return a new linked list that represents these frequencies.

• Start by defining a Solution class containing the elementFrequencies function, which takes a ListNode* representing the head of the input linked list.
• Utilize an unordered_map to store the frequencies of each value within the linked list. The map's key is the node value, and the value is a ListNode* pointing to a node in a new linked list that maintains frequency counts.
• Start by initializing a pointer, currentNode, to traverse the original linked list starting from its head. Also, maintain a freqHead pointer which serves as the head of the new frequency linked list.
• Traverse the list until currentNode becomes nullptr. For each element:
  • Check if the current node's value is already present in the freqMap:
    • If true, retrieve the associated node from freqMap and increment its value, which keeps count of the frequency.
    • If false, create a new ListNode initializing its value to 1 (as the current number appears for the first time), and insert it into the frequency linked list maintaining the insertion order.
• The map ensures that insertion and lookup operations are efficient, typically $O(1)$ on average.
• After completing the traversal, return the freqHead, which now points to the head of a newly formed linked list representing the frequencies of each distinct value in the original list.

This organized approach allows for an effective calculation of frequencies using the linear structure of linked lists combined with the efficiency of hash tables. The function returns a linked list where each node's value corresponds to the frequency of elements from the original list, ordered by their first occurrence.