Linked List Frequency - Practice Coding Problems

Linked List Frequency - Problem

Given the head of a linked list containing k distinct elements, return the head to a linked list of length k containing the frequency of each distinct element in the given linked list in any order.

The frequency of an element is the number of times it appears in the linked list.

Example: If the linked list is [1→2→1→3→2→2], the frequencies are: 1 appears 2 times, 2 appears 3 times, 3 appears 1 time. Return a linked list containing [2→3→1] (frequencies in any order).

Input & Output

Example 1 — Basic Case

$ Input: head = [1,2,1,3,2,2]

› Output: [2,3,1]

💡 Note: Element 1 appears 2 times, element 2 appears 3 times, element 3 appears 1 time. Return frequencies in any order.

Example 2 — All Unique

$ Input: head = [1,2,3]

› Output: [1,1,1]

💡 Note: Each element appears exactly once, so all frequencies are 1.

Example 3 — All Same

$ Input: head = [5,5,5,5]

› Output: [4]

💡 Note: Only one distinct element (5) appears 4 times, so return [4].

Constraints

1 ≤ length of linked list ≤ 10⁵
-10⁵ ≤ Node.val ≤ 10⁵
The linked list contains exactly k distinct elements

Visualization

Tap to expand

Understanding the Visualization

Input List

Linked list with repeated elements: [1,2,1,3,2,2]

Count Frequencies

Count how many times each element appears

Output List

New linked list with frequency counts: [2,3,1]

Key Takeaway

🎯 Key Insight: Use hash map to count frequencies in single pass, then build result linked list

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

Use a hash map to count element frequencies in a single pass through the linked list, then build a result linked list containing these frequency counts. The optimal approach has O(n) time and O(k) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Count Each Element Separately	O(n²)	O(k)	For each unique element, traverse entire list to count occurrences
Hash Map - Single Pass Frequency Count	O(n)	O(k)	Use hash map to count frequencies in one pass, then build result list

Brute Force - Count Each Element Separately — Algorithm Steps

Traverse list to collect unique elements
For each unique element, count occurrences by traversing entire list
Build result linked list with frequency counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Unique Elements

Scan list to collect unique values: [1, 2, 3]

Count Each Element

For each unique value, count occurrences by full scan

Build Result

Create new linked list with frequency counts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* head) {
    if (!head) return NULL;
    
    // Collect unique elements
    int uniqueVals[1000];
    int uniqueCount = 0;
    struct ListNode* curr = head;
    
    while (curr) {
        int found = 0;
        for (int i = 0; i < uniqueCount; i++) {
            if (uniqueVals[i] == curr->val) {
                found = 1;
                break;
            }
        }
        if (!found) {
            uniqueVals[uniqueCount++] = curr->val;
        }
        curr = curr->next;
    }
    
    // Count frequency for each unique element
    int frequencies[1000];
    for (int i = 0; i < uniqueCount; i++) {
        int count = 0;
        curr = head;
        while (curr) {
            if (curr->val == uniqueVals[i]) {
                count++;
            }
            curr = curr->next;
        }
        frequencies[i] = count;
    }
    
    // Build result linked list
    if (uniqueCount == 0) return NULL;
    
    struct ListNode* resultHead = malloc(sizeof(struct ListNode));
    resultHead->val = frequencies[0];
    resultHead->next = NULL;
    curr = resultHead;
    
    for (int i = 1; i < uniqueCount; i++) {
        curr->next = malloc(sizeof(struct ListNode));
        curr->next->val = frequencies[i];
        curr->next->next = NULL;
        curr = curr->next;
    }
    
    return resultHead;
}

struct ListNode* arrayToList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    struct ListNode* curr = head;
    for (int i = 1; i < size; i++) {
        curr->next = malloc(sizeof(struct ListNode));
        curr->next->val = arr[i];
        curr->next->next = NULL;
        curr = curr->next;
    }
    return head;
}

void printList(struct ListNode* head) {
    printf("[");
    struct ListNode* curr = head;
    int first = 1;
    while (curr) {
        if (!first) printf(",");
        printf("%d", curr->val);
        first = 0;
        curr = curr->next;
    }
    printf("]\n");
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int arr[1000];
    int size = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token && size < 1000) {
            arr[size++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    struct ListNode* head = arrayToList(arr, size);
    struct ListNode* result = solution(head);
    printList(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each of k unique elements, traverse n nodes to count occurrences

⚠ Quadratic Growth

Space Complexity

O(k)

Store k unique elements and create result list of k nodes

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Count Each Element Separately — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler