Create Linked List Frequency

Given the head of a linked list containing k distinct elements, the task is to return the head of linked list of length k containing the frequency of each distinct element in the given linked list in any order.

Example:

Input: head = {1,2,1,2,3}
Output: {2,2,1}
Explanation: There are 3 distinct elements in the list. The frequency of 1 is 2, the frequency of 2 is 2 and the frequency of 3 is 1. Hence, we return 2 -> 2 -> 1.
Please note that 1 -> 2 -> 2, 2 -> 1 -> 2 and 2 -> 2 -> 1 are also valid answers.

Input: head = {1,1,3,3,3}
Output: {2,3}
Explanation: There are 2 distinct elements in the list. The frequency of 1 is 2 and the frequency of 3 is 3. Hence, we return 2 -> 3.

Approach:

Create a hashmap called frequencies to store the frequency of each element. The key is the element, and the value is a ListNode with its frequency. Each ListNode stores its next pointer, so as long as we have a reference to the first node in the sequence, we can maintain the linked list of frequencies.

We create an empty node, freqHead, to store the head of the new linked list of frequencies. We traverse the original linked list, processing the nodes. If the value of current is not yet in the frequencies table, we create a new ListNode with the frequency 1 and add it to the hashmap. If the current's value is already in the hashmap, we increase the node's value by 1 at that key. When we create a new ListNode, we append it to the beginning of the new linked list.

Steps-by-step appraoch:

• Initialize a hashmap frequencies to store each element's frequency. The key is the element, and the value is a ListNode with its frequency.
• Initialize a ListNode current to head for iterating through the original linked list.
• Initialize a ListNode freqHead to null which will be the head of the linked list of frequencies.
• Loop through the nodes in the linked list while current != null:
  • If current.val is in frequencies:
    • Set a node, frequencyNode, to the node storing the frequency of element current.val.
    • Increment frequencyNode.val by 1.
  • Otherwise, this is a new element:
    • Create a new ListNode newFrequencyNode with the value 1 and set its next field to freqHead.
    • Set frequencies[current.val] to newFrequencyNode.
    • Set freqHead to newFrequencyNode.
• Set current to current.next to progress to the next node in the original linked list.
• Return freqHead.

Below is the implementation of the above approach:

#include <iostream>
#include <unordered_map>

using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode()
        : val(0)
        , next(nullptr)
    {
    }
    ListNode(int x)
        : val(x)
        , next(nullptr)
    {
    }
    ListNode(int x, ListNode* next)
        : val(x)
        , next(next)
    {
    }
};

ListNode* frequenciesOfElements(ListNode* head)
{
    unordered_map<int, ListNode*> frequencies;
    ListNode* current = head;
    ListNode* freqHead = nullptr;

    // Process the linked list, storing
    // frequency ListNodes in the hashtable
    while (current != nullptr) {

        // Increment frequency of existing element
        if (frequencies.find(current->val)
            != frequencies.end()) {
            ListNode* frequencyNode
                = frequencies[current->val];
            frequencyNode->val += 1;

            // New element, create hashtable entry with
            // frequency node
        }
        else {
            ListNode* newFrequencyNode
                = new ListNode(1, freqHead);
            frequencies[current->val] = newFrequencyNode;
            freqHead = newFrequencyNode;
        }
        current = current->next;
    }
    return freqHead;
}

int main()
{
    // Example linked list
    ListNode* head = new ListNode(1);
    head->next = new ListNode(1);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(2);
    head->next->next->next->next = new ListNode(2);
    head->next->next->next->next->next = new ListNode(3);

    // Get the list of frequencies
    ListNode* frequencies = frequenciesOfElements(head);

    // Print the frequencies
    while (frequencies != nullptr) {
        cout << frequencies->val << " ";
        frequencies = frequencies->next;
    }
    cout << endl;

    return 0;
}

import java.util.HashMap;
import java.util.Map;

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Main {
    public static ListNode frequenciesOfElements(ListNode head) {
        Map<Integer, ListNode> frequencies = new HashMap<>();
        ListNode current = head;
        ListNode freqHead = null;

        // Process the linked list, storing frequency ListNodes in the hashtable
        while (current != null) {
            // Increment frequency of existing element
            if (frequencies.containsKey(current.val)) {
                ListNode frequencyNode = frequencies.get(current.val);
                frequencyNode.val += 1;
            } else { // New element, create hashtable entry with frequency node
                ListNode newFrequencyNode = new ListNode(1, freqHead);
                frequencies.put(current.val, newFrequencyNode);
                freqHead = newFrequencyNode;
            }
            current = current.next;
        }
        return freqHead;
    }

    public static void main(String[] args) {
        // Example linked list
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(2);
        head.next.next.next.next.next = new ListNode(3);

        // Get the list of frequencies
        ListNode frequencies = frequenciesOfElements(head);

        // Print the frequencies
        while (frequencies != null) {
            System.out.print(frequencies.val + " ");
            frequencies = frequencies.next;
        }
        System.out.println();
    }
}

// This code is contributed by shivamgupta0987654321

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x=0, next=None):
        self.val = x
        self.next = next


def frequencies_of_elements(head):
    frequencies = {}
    current = head
    freq_head = None

    # Process the linked list, storing
    # frequency ListNodes in the hashtable
    while current is not None:

        # Increment frequency of existing element
        if current.val in frequencies:
            frequency_node = frequencies[current.val]
            frequency_node.val += 1

        # New element, create hashtable entry with
        # frequency node
        else:
            new_frequency_node = ListNode(1, freq_head)
            frequencies[current.val] = new_frequency_node
            freq_head = new_frequency_node

        current = current.next

    return freq_head


# Example linked list
head = ListNode(1)
head.next = ListNode(1)
head.next.next = ListNode(2)
head.next.next.next = ListNode(2)
head.next.next.next.next = ListNode(2)
head.next.next.next.next.next = ListNode(3)

# Get the list of frequencies
frequencies = frequencies_of_elements(head)

# Print the frequencies
current = frequencies
while current is not None:
    print(current.val, end=" ")
    current = current.next
print()

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

function frequenciesOfElements(head) {
    const frequencies = {};
    let current = head;
    let freqHead = null;

    // Process the linked list, storing
    // frequency ListNodes in the hashtable
    while (current !== null) {
        // Increment frequency of existing element
        if (current.val in frequencies) {
            const frequencyNode = frequencies[current.val];
            frequencyNode.val += 1;
        } else {
            // New element, create hashtable entry with
            // frequency node
            const newFrequencyNode = new ListNode(1, freqHead);
            frequencies[current.val] = newFrequencyNode;
            freqHead = newFrequencyNode;
        }
        current = current.next;
    }

    return freqHead;
}

// Example linked list
const head = new ListNode(1);
head.next = new ListNode(1);
head.next.next = new ListNode(2);
head.next.next.next = new ListNode(2);
head.next.next.next.next = new ListNode(2);
head.next.next.next.next.next = new ListNode(3);

// Get the list of frequencies
const frequencies = frequenciesOfElements(head);

// Collect frequencies into a single line string
let result = [];
let current = frequencies;
while (current !== null) {
    result.push(current.val);
    current = current.next;
}

// Print the frequencies in a single line
console.log(result.join(' '));

1 3 2 

Time complexity: O(n)
Auxiliary Space: O(n)