Problem Description

You are given the head of a linked list that contains k distinct elements (where elements may appear multiple times). Your task is to return a new linked list of length k where each node contains the frequency count of a distinct element from the original linked list.

The problem asks you to:

1. Count how many times each distinct element appears in the input linked list
2. Create a new linked list where each node's value is one of these frequency counts
3. The output linked list should have exactly k nodes (one for each distinct element)
4. The order of frequencies in the output doesn't matter

For example:

• If the input is [1,1,2,1,2,3], there are 3 distinct elements:
  • Element 1 appears 3 times
  • Element 2 appears 2 times
  • Element 3 appears 1 time
• The output would be [3,2,1] (the frequencies of each distinct element)

The solution uses a hash table (Counter) to track the frequency of each element value while traversing the input linked list. Then it creates a new linked list by iterating through the frequency values and constructing nodes with those frequencies as values. The use of dummy.next = ListNode(val, dummy.next) creates the new linked list in reverse order of iteration, but since order doesn't matter according to the problem, this is acceptable.

Intuition

The core insight is that we need to transform the linked list from containing element values to containing frequency counts. This naturally suggests a two-step process: first count, then build.

When we need to count occurrences of elements, a hash table (or dictionary) is the go-to data structure because it allows us to efficiently track and update counts as we traverse the list. Each time we encounter an element, we can increment its count in O(1) time.

The key observation is that we don't need to preserve any relationship between the original elements and their frequencies in the output - we only need the frequency values themselves. This means after counting, we can simply extract all the frequency values from our hash table and build a new linked list with these values.

For building the output linked list, we can use a dummy node technique. The clever part of the solution is using dummy.next = ListNode(val, dummy.next) which prepends each new node to the front of the list we're building. This is more efficient than appending to the end (which would require keeping track of the tail), and since the problem states that any order is acceptable, we can take advantage of this flexibility.

The approach is straightforward: traverse once to count (O(n) time), then build a new list with k frequency values (O(k) time). Since k ≤ n, the overall time complexity is O(n), which is optimal as we must examine every node at least once.

Learn more about Linked List patterns.

Solution Approach

The solution uses a Hash Table approach to solve this problem efficiently.

Step 1: Count Frequencies

We initialize a Counter object (which is a specialized dictionary in Python) to track the frequency of each element:

• cnt = Counter() creates an empty counter
• We traverse the linked list with a while loop: while head:
• For each node, we increment the count: cnt[head.val] += 1
• Move to the next node: head = head.next

After this traversal, cnt contains key-value pairs where keys are the distinct element values and values are their frequencies.

Step 2: Build the Result Linked List

We use the dummy node pattern to construct the output:

• dummy = ListNode() creates a dummy head node to simplify list construction
• We iterate through the frequency values: for val in cnt.values()
• For each frequency value, we create a new node and prepend it to the existing list: dummy.next = ListNode(val, dummy.next)
  • ListNode(val, dummy.next) creates a new node with value val and its next pointer pointing to the current first node
  • Setting dummy.next to this new node effectively adds it to the front of the list

Step 3: Return the Result

We return dummy.next, which skips the dummy node and gives us the actual head of the frequency list.

The key insight in the construction is that ListNode(val, dummy.next) allows us to prepend nodes efficiently. Each new node points to what was previously the first node, and then becomes the new first node. This builds the list in reverse order of iteration through the frequencies, but since the problem allows any order, this approach is both correct and efficient.

Time Complexity: O(n) where n is the number of nodes in the input list
Space Complexity: O(k) where k is the number of distinct elements

Example Walkthrough

Let's walk through a small example with the input linked list: [5, 5, 3, 5, 3, 7]

Step 1: Count Frequencies

Starting with an empty Counter, we traverse the linked list:

• Node 1: value = 5, cnt = {5: 1}
• Node 2: value = 5, cnt = {5: 2}
• Node 3: value = 3, cnt = {5: 2, 3: 1}
• Node 4: value = 5, cnt = {5: 3, 3: 1}
• Node 5: value = 3, cnt = {5: 3, 3: 2}
• Node 6: value = 7, cnt = {5: 3, 3: 2, 7: 1}

We have 3 distinct elements with frequencies: 5 appears 3 times, 3 appears 2 times, 7 appears 1 time.

Step 2: Build the Result Linked List

We create a dummy node and iterate through the frequency values [3, 2, 1]:

Initial state: dummy -> None

• First iteration (val = 3):

  • Create ListNode(3, dummy.next) where dummy.next is None
  • New node: 3 -> None
  • Set dummy.next to this new node
  • Result: dummy -> 3 -> None

• Second iteration (val = 2):

  • Create ListNode(2, dummy.next) where dummy.next is the node with value 3
  • New node: 2 -> 3 -> None
  • Set dummy.next to this new node
  • Result: dummy -> 2 -> 3 -> None

• Third iteration (val = 1):

  • Create ListNode(1, dummy.next) where dummy.next is the node with value 2
  • New node: 1 -> 2 -> 3 -> None
  • Set dummy.next to this new node
  • Result: dummy -> 1 -> 2 -> 3 -> None

Step 3: Return Result

Return dummy.next, which gives us the head of the list: [1, 2, 3]

This represents the frequencies of the distinct elements in the original list. The order [1, 2, 3] is different from how we might naturally think about it (3, 2, 1), but since the problem states any order is acceptable, this reverse construction through prepending is both correct and efficient.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the linked list.

• The first while loop traverses the entire linked list once to count frequencies: O(n)
• Building the Counter dictionary involves updating counts for each node: O(n) total operations
• The for loop iterates through the unique values in the Counter (at most n unique values): O(n) in worst case
• Each insertion operation in the for loop (creating a new ListNode) is O(1)
• Overall time complexity: O(n) + O(n) = O(n)

Space Complexity: O(n), where n is the length of the linked list.

• The Counter dictionary stores at most n key-value pairs (when all elements are unique): O(n)
• The output linked list will have at most n nodes (when all elements are unique): O(n)
• Additional variables like dummy and head pointer: O(1)
• Overall space complexity: O(n) + O(n) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Original Linked List

A common mistake is accidentally modifying the input linked list while traversing it. For example:

Incorrect approach:

def frequenciesOfElements(self, head: Optional[ListNode]) -> Optional[ListNode]:
    frequency_counter = Counter()
    # DON'T DO THIS - modifies the original list
    while head:
        frequency_counter[head.val] += 1
        head = head.next  # This changes the original head reference
  
    # Later code might assume head still points to the start
    # but head is now None!

Solution: Always use a separate pointer for traversal:

current = head  # Create a copy of the reference
while current:
    frequency_counter[current.val] += 1
    current = current.next  # Move the copy, not the original

2. Forgetting to Handle Empty Input

The code handles empty lists correctly due to Python's Counter and the dummy node pattern, but explicitly checking can make the code more readable and prevent edge case issues:

Enhanced solution:

def frequenciesOfElements(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head:  # Explicit empty list check
        return None
  
    # Rest of the implementation...

3. Confusion About List Construction Order

The line dummy_head.next = ListNode(frequency, dummy_head.next) builds the list in reverse order of iteration. While this doesn't matter for this problem, developers might expect the output order to match the iteration order:

If order matters (alternative approach):

# To maintain iteration order, keep track of the tail
dummy_head = ListNode()
tail = dummy_head

for frequency in frequency_counter.values():
    tail.next = ListNode(frequency)
    tail = tail.next

return dummy_head.next

4. Not Importing Required Modules

Forgetting to import Counter from collections will cause a NameError:

Fix: Always ensure proper imports:

from collections import Counter  # Don't forget this import!

5. Assuming Node Values are Hashable

The solution assumes that head.val can be used as a dictionary key. If node values were unhashable types (like lists), this would fail. While this is unlikely in typical LeetCode problems, it's worth noting for real-world applications.