## Description

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:

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:

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:

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

## Solutions

### Solution 1: Hash Table

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.

• /**
* 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 {
Map<Integer, Integer> cnt = new HashMap<>();
}
ListNode dummy = new ListNode();
for (int val : cnt.values()) {
dummy.next = new ListNode(val, dummy.next);
}
return dummy.next;
}
}

• /**
* 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:
unordered_map<int, int> cnt;
}
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:
#     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()
dummy = ListNode()
for val in cnt.values():
dummy.next = ListNode(val, dummy.next)
return dummy.next


• /**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
cnt := map[int]int{}
}
dummy := &ListNode{}
for _, val := range cnt {
dummy.Next = &ListNode{val, dummy.Next}
}
return dummy.Next
}

• /**
* 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();