Linked List Frequency solution and explanation
2 more videos on this problem
The problem
Given the head of a linked list containing k distinct elements, return the head to a linked list of length k containing the frequency of each distinct element in the given linked list in any order.
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 <= 105
Approach overview
Problem Overview: You receive the head of a singly linked list and need to compute how frequently each value appears. The task is essentially a counting problem on top of a linked list: traverse the list, track how many times each value occurs, and return those frequencies.
Approach 1: Brute Force Counting (O(n²) time, O(1) space)
The straightforward idea is to count occurrences for each node by scanning the rest of the list. For every node, iterate through the entire linked list and count how many nodes share the same value. To avoid duplicate reporting, you can mark already processed values or skip values that appeared earlier in the traversal. This method relies only on repeated iteration over the linked list structure, so it uses constant extra memory, but the nested traversal results in O(n²) time.
Approach 2: Hash Table Counting (O(n) time, O(k) space)
The optimal solution uses a hash table to track frequencies. Traverse the linked list once and store counts in a map where the key is the node value and the value is its frequency. Each step performs a constant-time hash lookup and increment operation. After the traversal finishes, iterate through the map values (or build the required result structure) to return the frequency counts.
This works because counting problems benefit from constant-time key lookups provided by hashing. Every node is processed exactly once, so the runtime is O(n). The extra space is O(k), where k is the number of distinct values stored in the hash table. This approach also fits naturally with typical counting patterns used across many interview problems.
Recommended for interviews: The hash table approach is what interviewers expect. It shows you recognize a counting pattern and immediately reach for a map to avoid repeated scans. Mentioning the brute force method first demonstrates baseline reasoning, but implementing the O(n) hash-based solution shows stronger problem-solving instincts.
Solution
We use a hash table cnt to record the occurrence times of each element value in the linked list, then traverse the values of the hash table to construct a new linked list.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the linked list.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def frequenciesOfElements(self, head: Optional[ListNode]) -> Optional[ListNode]:
cnt = Counter()
while head:
cnt[head.val] += 1
head = head.next
dummy = ListNode()
for val in cnt.values():
dummy.next = ListNode(val, dummy.next)
return dummy.next/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode frequenciesOfElements(ListNode head) {
Map<Integer, Integer> cnt = new HashMap<>();
for (; head != null; head = head.next) {
cnt.merge(head.val, 1, Integer::sum);
}
ListNode dummy = new ListNode();
for (int val : cnt.values()) {
dummy.next = new ListNode(val, dummy.next);
}
return dummy.next;
}
}/**
* 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) {}
* };
*/
class Solution {
public:
ListNode* frequenciesOfElements(ListNode* head) {
unordered_map<int, int> cnt;
for (; head; head = head->next) {
cnt[head->val]++;
}
ListNode* dummy = new ListNode();
for (auto& [_, val] : cnt) {
dummy->next = new ListNode(val, dummy->next);
}
return dummy->next;
}
};/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function frequenciesOfElements(head: ListNode | null): ListNode | null {
const cnt: Map<number, number> = new Map();
for (; head; head = head.next) {
cnt.set(head.val, (cnt.get(head.val) || 0) + 1);
}
const dummy = new ListNode();
for (const val of cnt.values()) {
dummy.next = new ListNode(val, dummy.next);
}
return dummy.next;
}/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func frequenciesOfElements(head *ListNode) *ListNode {
cnt := map[int]int{}
for ; head != nil; head = head.Next {
cnt[head.Val]++
}
dummy := &ListNode{}
for _, val := range cnt {
dummy.Next = &ListNode{val, dummy.Next}
}
return dummy.Next
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Nested Traversal | O(n²) | O(1) | Useful for understanding the basic counting logic when avoiding extra memory |
| Hash Table Counting | O(n) | O(k) | General case and interview-preferred solution for counting frequencies efficiently |
Frequently asked questions
Is Linked List Frequency easy or hard?
Linked List Frequency is considered an Easy problem. The core idea is recognizing it as a counting problem and applying a hash map while traversing the linked list once.
Linked List Frequency Python/Java solution
In both Python and Java, the solution uses a hash map or dictionary to store value frequencies while iterating through the linked list. Python typically uses a dictionary or collections.Counter, while Java uses a HashMap<Integer, Integer>. Both implementations achieve O(n) time complexity.
How to solve Linked List Frequency in O(n)?
Traverse the linked list once and maintain a hash map where the key is the node value and the value is its count. For every node, increment the corresponding value in the map. After the traversal, the map contains the frequency of every value, giving an O(n) solution.
What is the best approach for Linked List Frequency?
The most efficient approach uses a hash table to count how many times each value appears while traversing the linked list once. Each node updates a frequency map using constant-time hash lookups. This results in O(n) time complexity and O(k) space complexity, where k is the number of distinct values.
Is Linked List Frequency asked at Google/Amazon/Meta?
Frequency-counting problems using hash tables appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the underlying pattern of counting values with a hash map is very common in coding interviews.
What data structure is used in Linked List Frequency?
A hash table (hash map or dictionary) is the primary data structure used. It stores each distinct value from the linked list as a key and tracks how many times it appears. The input itself is processed through standard linked list traversal.
What is the time complexity of Linked List Frequency?
The optimal solution runs in O(n) time because the linked list is traversed exactly once and each frequency update in the hash map takes constant time. A brute force method that scans the list repeatedly would take O(n^2) time.