Linked List Frequency - Solution & Explanation

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.