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.

class Solution {
    public ListNode countElements(ListNode head) {
        Map<Integer, ListNode> countMap = new HashMap<>();
        ListNode currentNode = head;
        ListNode resultHead = null;

        while (currentNode != null) {
            if (countMap.containsKey(currentNode.val)) {
                ListNode countNode = countMap.get(currentNode.val);
                countNode.val += 1;
            } else {
                ListNode newCountNode = new ListNode(1, resultHead);
                countMap.put(currentNode.val, newCountNode);
                resultHead = newCountNode;
            }
            currentNode = currentNode.next;
        }
        return resultHead;
    }
}

The Java program provided creates a list that consists of the frequency of each element in the input LinkedList. The key steps in the code can be summarized as follows:

• Initialize a HashMap to keep track of the count of each unique value found in the list.
• Traverse through the input linked list using a while loop.
• For each element in the list:
  • Check if the element's value (currentNode.val) already exists in the HashMap.
  • If it exists, increment the count stored in the corresponding node (countNode) in the HashMap.
  • If it doesn't exist, create a new ListNode with a count of one and add it to the HashMap and update resultHead to point to this new node.
• Return the resultHead, which points to the linked list of counts of each element.

Remember, each value in the returned list represents the frequency of that element in the original list, linked in the order they first appeared. Each node’s value corresponds to the frequency, and their order in the list follows the order of original appearance in the input list.

class Solution:
    def countElementOccurrences(self, start: Optional[ListNode]) -> Optional[ListNode]:
        element_count = {}
        node_iter = start
        count_start = None

        while node_iter is not None:
            val = node_iter.val
            if val in element_count:
                existing_node = element_count[val]
                existing_node.val += 1
            else:
                new_node = ListNode(1, count_start)
                element_count[val] = new_node
                count_start = new_node
            node_iter = node_iter.next

        return count_start

This Python program aims to determine the frequency of elements in a linked list. The provided function, countElementOccurrences, accepts the head of a linked list as its parameter and returns a new linked list where each node's value represents the frequency of an element from the original list.

Understand the steps below for achieving this task:

1. Initialize a dictionary, element_count, which maps element values from the original list to nodes in the resulting frequency list.
2. Set node_iter to start at the head of the original linked list and count_start to None. count_start will stand as the head of the resulting frequency list.
3. Iterate through the original list with node_iter. For each node:

• Retrieve the node's value (val).
• If val is present in element_count, increment its corresponding node's value in the frequency list by 1.
• Otherwise, create a new node in the frequency list with a value of 1 and adjust pointers accordingly.

1. Move to the next node in the original list until all nodes are processed.

When the iteration completes, count_start serves as the head of a linked list where each node's value corresponds to the frequency of a unique element from the original list. The list may not necessarily be in the same order as the original due to the nature of dictionary key insertions. Each node in the frequency linked list directly shows the count of occurrences for its respective element from the input list.