Linked List Frequency
01 · Problem
You are given the head of a singly linked list of integers. Build and return a new linked list that contains one node per distinct value of the input, where each node stores how many times that value occurs.
The output nodes must appear in the order in which each distinct value is first seen while walking the input from the head. The output therefore has exactly as many nodes as there are distinct values; the values themselves are not part of the output, only their counts.
02 · Examples
head = [4,8,8,4,2,8]
[2,3,1]
Distinct values in order of first appearance are 4, 8, 2. Value 4 occurs 2 times, 8 occurs 3 times, and 2 occurs once.
head = [10,10,10,20,20,30]
[3,2,1]
10 appears 3 times, then 20 appears 2 times, then 30 appears once.
head = [7]
[1]
A single node gives a single distinct value with frequency 1.
03 · Constraints
- 01The number of nodes in the list is in the range [1, 105].
- 02-105 <= Node.val <= 105
- 03The output list is ordered by the first occurrence of each distinct value in the input.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(d)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.