3063. Linked List Frequency

EasyHash TableLinked ListCounting

Problem Description

In this problem, we are given the head of a singly linked list that contains an unspecified number of nodes. Each node in the linked list contains an integer value, and all the elements in the linked list are said to be distinct. Our objective is to create a new linked list that represents the frequency of each distinct element found in the original linked list. The length of the new linked list will be equal to the number of distinct elements (k) in the original list, and the values of nodes in the new list are the frequencies of the corresponding elements, unordered.

For instance, if the original list contained the elements [1,1,2,1,2,3], there are 3 distinct elements, and the new list should contain [3,2,1] to represent the frequencies of elements 1, 2, and 3, respectively. It is important to note that the elements in the new list output do not need to be in any particular order and represent the count of how many times each element occurs in the original list.

Intuition

To solve this problem, we utilize a hash table (dictionary in Python) to keep track of the frequency or count of each element as we traverse the original linked list. Since the elements in the linked list are distinct, each key in the hash table uniquely identifies an element, and the associated value represents the frequency of that element.

The process begins by initializing an empty hash table and then iterating through each node in the linked list until we reach the end. For each node, we increment the count of the node's value in the hash table. After completing the traversal, we will have a complete record of the frequencies of all the distinct elements in the original list.

Next, we generate a new linked list from the frequency counts stored in the hash table. For each frequency count in the hash table, we create a new node with that frequency as its value and insert it at the beginning of the new linked list. This approach conveniently constructs the new linked list in reverse order, which is acceptable because the problem statement does not require the frequencies to be in a specific order.

In summary, the solution involves two primary steps:

Traverse the original linked list and record the frequency of each element.
Traverse the hash table and construct the new linked list using the frequencies recorded.

The time complexity of this algorithm is linear, O(n), because we iterate through each element of the original linked list once. The space complexity is also linear, O(k), where k is the number of distinct elements in the list, for storing the frequency counts in the hash table.

Learn more about Linked List patterns.

Solution Approach

The implementation of the solution follows a straightforward approach, making use of two core concepts—hash tables and linked lists. Below is an explanation of how each part of the solution is brought together:

Hash Table to Record Frequencies

A hash table is used to map unique elements to their frequency. In Python, the collections.Counter class is an excellent fit for this purpose, as it automatically initializes dictionary keys with a default count of 0.

As we iterate over the original linked list, we increment the count for the value of each node:

cnt = Counter()
while head:
    cnt[head.val] += 1
    head = head.next

For every node in the linked list, head.val is used to reference the node's value, which serves as the key in the hash table cnt. The corresponding value in the hash table is incremented to keep track of the frequency of the element.

Constructing the New Linked List

The next step is to construct the new linked list using the frequencies stored in the hash table. We create a dummy head node to simplify the process of adding new nodes to the linked list. This allows us to insert nodes without checking if the list is empty:

dummy = ListNode()

We iterate over the hash table's values, creating a new node for each frequency:

for val in cnt.values():
    dummy.next = ListNode(val, dummy.next)

Here, we're inserting each new node at the beginning of the new linked list so that the dummy's next always points to the latest node created. The order doesn't matter according to the problem statement.

By the end of this loop, we have a new linked list that starts right after the dummy node. The new list contains the frequencies of distinct elements as its node values.

Finally, we return the next node of dummy, which is the head of the new linked list containing the frequencies:

return dummy.next

In conclusion, the solution combines the efficient counting using a hash table with simple list manipulation to generate the required output. The elegance of the solution lies in its utilization of Python's built-in Counter to handle the frequency tracking and the dummy node that circumvents the need for special cases while constructing the new list.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through an example to illustrate the solution approach with a small sample linked list. Suppose our original linked list is 4 -> 2 -> 4 -> 3, representing the elements [4, 2, 4, 3]. We want to create a new linked list that shows how frequently each distinct element occurs.

Step 1: Using a Hash Table to Record Frequencies

First, we initialize an empty hash table (Counter) and begin iterating over the linked list. Here's how the counter changes as we traverse the list:

After encountering the first element (4), the counter is {4: 1}.
The second element is (2), updating the counter to {4: 1, 2: 1}.
The third element is again (4), so we increment its count: {4: 2, 2: 1}.
Finally, we encounter (3), and the counter becomes {4: 2, 2: 1, 3: 1}.

Now we have a hash table that contains the frequency of each distinct element from the original list.

Step 2: Constructing the New Linked List

With the frequency counts stored, we proceed to create the new linked list:

We initialize a new linked list with a dummy head.
Iterate over the counter values: (2, 1, 1).
For each frequency, we create a new node and add it to the front of the list.

Here are the steps visualized:

New node with value 2 -> new list is: dummy -> 2
New node with value 1 -> new list is: dummy -> 1 -> 2
New node with value 1 -> new list is: dummy -> 1 -> 1 -> 2

We've inserted each new node at the beginning, so after we're done, our new list (ignoring dummy) looks like: 1 -> 1 -> 2.

Remembering the order is irrelevant; this new list represents the frequencies of elements 4, 2, and 3 respectively: [2, 1, 1]. Now, we return the first actual node after the dummy, which is the head of the new linked list containing the frequencies.

Therefore, given the original linked list 4 -> 2 -> 4 -> 3, our algorithm correctly outputs a new linked list with elements representing the frequencies [2, 1, 1]. The number 4 appears twice, and numbers 2 and 3 appear once in the original list.

Solution Implementation

1from collections import Counter
2
3# Definition for singly-linked list.
4class ListNode:
5    def __init__(self, val=0, next_node=None):
6        self.val = val
7        self.next = next_node
8
9class Solution:
10    def frequenciesOfElements(self, head: Optional[ListNode]) -> Optional[ListNode]:
11        # Use Counter to count occurrences of each element
12        count = Counter()
13      
14        # Iterate through the linked list and count frequencies
15        current_node = head
16        while current_node:
17            count[current_node.val] += 1
18            current_node = current_node.next
19      
20        # Create a dummy node to make adding new nodes easier
21        dummy_node = ListNode()
22        tail = dummy_node  # Tail will be used to keep track of the last node
23      
24        # Iterate through the frequencies and create a new linked list
25        # with the frequency values of each element in the same order they appear in the count
26        for frequency in count.values():
27            # Add a new node with the frequency to the new list
28            tail.next = ListNode(frequency)
29            tail = tail.next  # Move the tail to the new last node
30      
31        # Return the head of the new linked list which contains the frequencies
32        return dummy_node.next
33

1import java.util.HashMap;
2import java.util.Map;
3
4/**
5 * Definition for singly-linked list.
6 */
7class ListNode {
8    int val;
9    ListNode next;
10    ListNode() {}
11    ListNode(int val) { this.val = val; }
12    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
13}
14
15class Solution {
16    /**
17     * Calculates frequency of each element in the linked list
18     * and returns a linked list of frequencies.
19     *
20     * @param head The head of the singly-linked list.
21     * @return The head of a new linked list representing frequencies of elements.
22     */
23    public ListNode frequenciesOfElements(ListNode head) {
24        // HashMap to store the frequency count of each element in the list
25        Map<Integer, Integer> frequencyMap = new HashMap<>();
26      
27        // Traverse the linked list and update the frequency count for each element
28        ListNode current = head;
29        while (current != null) {
30            // If the element is already in the map, increment the frequency, 
31            // otherwise add the element with frequency 1
32            frequencyMap.merge(current.val, 1, Integer::sum);
33            // Move to the next node
34            current = current.next;
35        }
36      
37        // Dummy node as a placeholder to start building the result list
38        ListNode dummy = new ListNode();
39        ListNode resultTail = dummy;
40      
41        // Iterate over the frequencies in the map to create a new list
42        for (int frequency : frequencyMap.values()) {
43            // Insert each frequency at the front of the list
44            resultTail.next = new ListNode(frequency);
45            resultTail = resultTail.next;
46        }
47      
48        // Return the head of the new list which contains the frequencies
49        return dummy.next;
50    }
51}
52

1#include <unordered_map>
2
3// Definition for singly-linked list.
4struct ListNode {
5    int val;            // The value stored within the node
6    ListNode *next;     // Pointer to the next node in the list
7    ListNode() : val(0), next(nullptr) {} // Default constructor initializing 'val' to 0 and 'next' to nullptr
8    ListNode(int x) : val(x), next(nullptr) {} // Constructor initializing 'val' with given value and 'next' to nullptr
9    ListNode(int x, ListNode *next) : val(x), next(next) {} // Constructor initializing both 'val' and 'next' with given values
10};
11
12class Solution {
13public:
14    ListNode* frequenciesOfElements(ListNode* head) {
15        // An unordered map that will store frequency of each element
16        unordered_map<int, int> elementFrequencies;
17      
18        // Iterate over the linked list and count the occurrences of each element
19        for (ListNode* cur = head; cur != nullptr; cur = cur->next) {
20            elementFrequencies[cur->val]++;
21        }
22
23        // A dummy node that simplifies list operations by removing the necessity to handle special cases for head.
24        ListNode* dummyHead = new ListNode();
25
26        // Adding the frequency values to a new list, maintaining the order of the elements
27        // Looping through the map and creating a new node with a frequency value for each element
28        for (auto &elementFrequency : elementFrequencies) {
29            dummyHead->next = new ListNode(elementFrequency.second, dummyHead->next);
30        }
31
32        // The actual head of the new list is the next of dummy node
33        ListNode* resultList = dummyHead->next;
34
35        // Cleaning up the dummy head node to prevent memory leak
36        delete dummyHead;
37
38        // Return the head of the list containing the frequencies
39        return resultList;
40    }
41};
42

1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5  val: number;
6  next: ListNode | null;
7  constructor(val?: number, next?: ListNode | null) {
8    this.val = (val===undefined ? 0 : val);
9    this.next = (next===undefined ? null : next);
10  }
11}
12
13/**
14 * Calculates the frequency of each element in a linked list and 
15 * creates a new linked list with the count of each element.
16 * @param head The head of the input linked list.
17 * @returns The head of the new linked list containing frequencies.
18 */
19function frequenciesOfElements(head: ListNode | null): ListNode | null {
20  // Create a map to keep track of the frequency count of each element.
21  const frequencyCount: Map<number, number> = new Map();
22
23  // Iterate over the linked list and update the count of each element.
24  let currentNode = head;
25  while (currentNode !== null) {
26    const currentValue = currentNode.val;
27    const currentCount = frequencyCount.get(currentValue) || 0;
28    frequencyCount.set(currentValue, currentCount + 1);
29    currentNode = currentNode.next;
30  }
31
32  // Initialize a dummy node to simplify insertions.
33  const dummyHead = new ListNode();
34  let tail = dummyHead;
35
36  // Iterate over the frequency count map and add the frequencies to the new linked list.
37  for (const frequency of frequencyCount.values()) {
38    tail.next = new ListNode(frequency);
39    tail = tail.next;
40  }
41
42  // Return the next of dummy node which points to head of the frequency list.
43  return dummyHead.next;
44}
45

Time and Space Complexity

The time complexity of the code is O(n), where n is the number of nodes in the linked list. This is because the algorithm must traverse each node once to count the frequency of its value, which is done in a single pass.

The space complexity is also O(n) because a Counter is used to store the frequency of each distinct element in the linked list. In the worst case, all elements are unique, and the counter will have n key-value pairs.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know