Linked List Frequency

Problem

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

Examples

Example 1:

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

Example 2:

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

Example 3:

Input: head = [6,5,4,3,2,1]
Output: [1,1,1,1,1,1]
Explanation: There are `6` distinct elements in the list. The frequency of
each of them is `1`. Hence, we return `1 -> 1 -> 1 -> 1 -> 1 -> 1`.

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 1 <= Node.val <= 10^5

Solution

Method 1 – Hash Map Frequency Count (1)

Intuition

We need to count the frequency of each distinct value in the linked list. Using a hash map allows us to efficiently count occurrences as we traverse the list, then we can build a new linked list from the frequency values.

Approach

1. Initialize an empty hash map to store frequencies.
2. Traverse the linked list, incrementing the count for each node's value in the map.
3. After traversal, create a new linked list where each node contains a frequency from the map (order does not matter).
4. Return the head of the new linked list.

Code

C++

class Solution {
public:
    ListNode* frequenciesOfElements(ListNode* head) {
        unordered_map<int, int> freq;
        for (auto p = head; p; p = p->next) freq[p->val]++;
        ListNode* dummy = new ListNode(0), *cur = dummy;
        for (auto& [_, f] : freq) {
            cur->next = new ListNode(f);
            cur = cur->next;
        }
        return dummy->next;
    }
};

Go

func frequenciesOfElements(head *ListNode) *ListNode {
    freq := map[int]int{}
    for p := head; p != nil; p = p.Next {
        freq[p.Val]++
    }
    dummy := &ListNode{}
    cur := dummy
    for _, f := range freq {
        cur.Next = &ListNode{Val: f}
        cur = cur.Next
    }
    return dummy.Next
}

Java

class Solution {
    public ListNode frequenciesOfElements(ListNode head) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (ListNode p = head; p != null; p = p.next) freq.put(p.val, freq.getOrDefault(p.val, 0) + 1);
        ListNode dummy = new ListNode(0), cur = dummy;
        for (int f : freq.values()) {
            cur.next = new ListNode(f);
            cur = cur.next;
        }
        return dummy.next;
    }
}

Kotlin

class Solution {
    fun frequenciesOfElements(head: ListNode?): ListNode? {
        val freq = mutableMapOf<Int, Int>()
        var p = head
        while (p != null) {
            freq[p.`val`] = freq.getOrDefault(p.`val`, 0) + 1
            p = p.next
        }
        val dummy = ListNode(0)
        var cur = dummy
        for (f in freq.values) {
            cur.next = ListNode(f)
            cur = cur.next!!
        }
        return dummy.next
    }
}

Python

class Solution:
    def frequenciesOfElements(self, head: Optional[ListNode]) -> Optional[ListNode]:
        freq: dict[int, int] = {}
        p = head
        while p:
            freq[p.val] = freq.get(p.val, 0) + 1
            p = p.next
        dummy = ListNode(0)
        cur = dummy
        for f in freq.values():
            cur.next = ListNode(f)
            cur = cur.next
        return dummy.next

Rust

impl Solution {
    pub fn frequencies_of_elements(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        let mut node = head.as_ref();
        while let Some(n) = node {
            *freq.entry(n.val).or_insert(0) += 1;
            node = n.next.as_ref();
        }
        let mut dummy = Box::new(ListNode::new(0));
        let mut cur = &mut dummy;
        for &f in freq.values() {
            cur.next = Some(Box::new(ListNode::new(f)));
            cur = cur.next.as_mut().unwrap();
        }
        dummy.next
    }
}

TypeScript

class Solution {
    frequenciesOfElements(head: ListNode | null): ListNode | null {
        const freq = new Map<number, number>();
        let p = head;
        while (p) {
            freq.set(p.val, (freq.get(p.val) || 0) + 1);
            p = p.next;
        }
        const dummy = new ListNode(0);
        let cur = dummy;
        for (const f of freq.values()) {
            cur.next = new ListNode(f);
            cur = cur.next;
        }
        return dummy.next;
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the number of nodes in the list. We traverse the list once to count and once to build the result.
• 🧺 Space complexity: O(k), where k is the number of distinct elements, for the hash map and the result list.