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:
[1, 105].1 <= Node.val <= 105Problem 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.
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.
Python
Java
C++
Go
TypeScript
| 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 |
3063. Linked List Frequency - Week 2/5 Leetcode March Challenge • Programming Live with Larry • 356 views views
Watch 1 more video solutions →Practice Linked List Frequency with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor