We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Linked List Frequency

Number: 3359

Difficulty: Easy

Paid? Yes

Companies: N/A

Problem Description

Given the head of a linked list containing k distinct elements, return the head to a new linked list of length k where each node represents the frequency of a distinct element from the input list. The order of the frequency nodes in the new linked list can be arbitrary.

Key Insights

  • Use a hash table (or dictionary) to count the frequency of each element while traversing the input linked list.
  • The number of unique keys in the hash table will be exactly k, where k is the number of distinct elements in the list.
  • After counting, build the resulting linked list by iterating over the frequency values in the hash table.
  • The approach requires two passes: one for counting and one for building the new list, ensuring an efficient solution.

Space and Time Complexity

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 (with k ≤ n).

Solution

The solution involves two main steps. First, traverse the linked list to count the frequency of each element using a hash table. Then, iterate through the hash table's values to construct a new linked list where each node contains one of the frequency counts. This approach efficiently leverages a hash table to simplify the counting process and enables building the result in a single additional pass.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def linkedListFrequency(head: ListNode) -> ListNode:
    # Dictionary to hold frequency count for each value.
    count = {}
    current = head
    while current:
        count[current.val] = count.get(current.val, 0) + 1
        current = current.next
    
    # Create a dummy node to simplify list construction.
    dummy = ListNode(0)
    tail = dummy
    # Build a new linked list based on the frequency counts.
    for freq in count.values():
        tail.next = ListNode(freq)
        tail = tail.next
    
    # Return the head of the frequency linked list.
    return dummy.next
← Back to All Questions