LeetCode 3063 - Linked List Frequency

LeetCode Problem 3063

Difficulty: 🟢 Easy
Topics: Hash Table, Linked List, Counting

Solution

Problem Understanding

This problem asks us to analyze a singly-linked list of integers and produce a new linked list containing the frequencies of each distinct element in the input list. Specifically, given the head of a linked list containing k distinct elements, we are to return another linked list of length k where each node represents the count of how many times a distinct element appeared in the original list. The order of these frequency nodes does not matter, meaning any permutation of the counts is acceptable.

The input is a standard singly-linked list, where each node contains an integer value (Node.val) and a pointer to the next node (Node.next). The constraints indicate that the number of nodes can be up to 105, and each node value is between 1 and 105. This suggests that an efficient algorithm is necessary because a naive approach that repeatedly scans the list could become too slow.

Edge cases include a linked list with a single element (the output list would also have a single node with value 1), or a list where all elements are unique (the output list would have all ones). The problem guarantees at least one node exists and all node values are integers within the specified range.

Approaches

The brute-force approach would be to iterate through each node and, for every node, count how many times that value appears in the entire list. This would involve nested iteration: the outer loop goes through each node, and the inner loop counts occurrences. While this produces the correct answer, the time complexity is O(n²), which is unacceptable for lists with up to 105 nodes.

The optimal approach leverages a hash table (dictionary in Python, map in Go) to count occurrences in a single pass. By iterating once through the linked list, we can store each element's frequency in the hash table. Then we construct a new linked list from these frequency values. This reduces the time complexity to O(n) while using O(k) additional space for the hash table, where k is the number of distinct elements.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	For each node, scan the entire list to count occurrences. Too slow for large n.
Optimal	O(n)	O(k)	Single-pass counting with a hash table, then build the frequency list. Efficient and scalable.

Algorithm Walkthrough

1. Initialize an empty hash table (frequency_map) to store counts of each distinct value.
2. Iterate through the input linked list starting from head.

• For each node, increment its value's count in the hash table.

3. After the iteration, the hash table contains every distinct element and its frequency.
4. Create a new dummy head node (dummy) for the result linked list to simplify construction.
5. Iterate through the frequency values stored in the hash table.

• For each frequency, create a new linked list node with that value and append it to the result list.

6. Return dummy.next as the head of the constructed frequency linked list.

Why it works: Each element in the original linked list is counted exactly once during the iteration, guaranteeing that the hash table reflects the correct frequency for all distinct values. Constructing the linked list from these counts ensures that every frequency appears exactly once, matching the problem requirement.

Python Solution

# 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]:
        from collections import defaultdict

        frequency_map = defaultdict(int)
        current = head

        # Count frequencies
        while current:
            frequency_map[current.val] += 1
            current = current.next

        # Build the frequency linked list
        dummy = ListNode(0)
        tail = dummy
        for freq in frequency_map.values():
            tail.next = ListNode(freq)
            tail = tail.next

        return dummy.next

In this Python implementation, we use a defaultdict to simplify frequency counting. The first loop iterates through the original list, updating the frequency map. The second loop constructs the output linked list from the values in the map. Using a dummy node avoids edge-case checks for an empty result list and simplifies appending new nodes.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func frequenciesOfElements(head *ListNode) *ListNode {
    freqMap := make(map[int]int)
    current := head

    // Count frequencies
    for current != nil {
        freqMap[current.Val]++
        current = current.Next
    }

    // Build the frequency linked list
    dummy := &ListNode{}
    tail := dummy
    for _, freq := range freqMap {
        tail.Next = &ListNode{Val: freq}
        tail = tail.Next
    }

    return dummy.Next
}

In Go, map[int]int serves as the hash table for counting. The iteration and list construction logic mirrors the Python version. Go-specific considerations include using pointers for list nodes and checking for nil instead of None.

Worked Examples

Example 1: head = [1,1,2,1,2,3]

Step	Current Node	frequency_map	Output List
1	1	{1:1}	[]
2	1	{1:2}	[]
3	2	{1:2, 2:1}	[]
4	1	{1:3, 2:1}	[]
5	2	{1:3, 2:2}	[]
6	3	{1:3, 2:2, 3:1}	[]
Construct	-	-	[3,2,1] (order can vary)

Example 2: head = [1,1,2,2,2]

Step	Current Node	frequency_map	Output List
1	1	{1:1}	[]
2	1	{1:2}	[]
3	2	{1:2, 2:1}	[]
4	2	{1:2, 2:2}	[]
5	2	{1:2, 2:3}	[]
Construct	-	-	[2,3]

Example 3: head = [6,5,4,3,2,1]

Step	Current Node	frequency_map	Output List
1-6	6→1	{6:1,5:1,4:1,3:1,2:1,1:1}	[]
Construct	-	-	[1,1,1,1,1,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single traversal of the input linked list to build the frequency map, then iterate over k distinct frequencies to build the output list.
Space	O(k)	Hash map stores frequency counts for k distinct elements; output list uses O(k) space as well.

The time complexity is linear in the number of nodes, and space scales with the number of distinct elements rather than total nodes, making this efficient even for the upper bound of 105 nodes.

Test Cases

# Provided examples
assert Solution().frequenciesOfElements(ListNode.from_list([1,1,2,1,2,3])).to_list() in ([3,2,1],[3,1,2],[2,3,1],[2,1,3],[1,2,3],[1,3,2])
assert Solution().frequenciesOfElements(ListNode.from_list([1,1,2,2,2])).to_list() in ([2,3],[3,2])
assert Solution().frequenciesOfElements(ListNode.from_list([6,5,4,3,2,1])).to_list() in ([1,1,1,1,1,1],)

# Edge cases
assert Solution().frequenciesOfElements(ListNode.from_list([1])).to_list() == [1]  # Single element
assert Solution().frequenciesOfElements(ListNode.from_list([1,2,3,4,5])).to_list() in ([1,1,1,1,1],)
assert Solution().frequenciesOfElements(ListNode.from_list([2,2,2,2,2])).to_list() == [5]  # All elements same

Test	Why
[1,1,2,1,2,3]	Tests multiple duplicates with more than 2 distinct elements.
[1,1,2,2,2]	Tests different frequency counts.
[6,5,4,3,2,1]	Tests all unique elements.
[1]	Tests minimal input.
[1,2,3,4,5]	Tests all unique elements for larger list.
[2,