Recuento de Nodes en una LinkedList cuyo valor es igual a su frecuencia

Dada una lista enlazada individualmente, la tarea es contar el número de Nodes cuyo valor de datos es igual a su frecuencia. 

Ejemplos: 

Entrada: Lista enlazada = 2 -> 3 -> 3 -> 3 -> 4 -> 2 
Salida: 2 
La frecuencia del elemento 2 es 2 
La frecuencia del elemento 3 es 3 
La frecuencia del elemento 4 es 1 
Entonces, 2 y 3 son elementos que tienen la misma frecuencia que su valor

Entrada: Lista enlazada = 1 -> 2 -> 3 -> 4 -> 5 -> 6 
Salida: 1

Recomendado: pruebe su enfoque en {IDE} primero, antes de pasar a la solución.

Enfoque: 
El enfoque para resolver este problema es el siguiente

• Iterar sobre la lista enlazada y almacenar la frecuencia de cada elemento de la array usando un mapa
• Iterar sobre el mapa y contar el número de elementos cuya frecuencia es igual a su valor

A continuación se muestra la implementación del enfoque anterior:

/* Link list node */
#include <bits/stdc++.h>
using namespace std;
 
class Node {
public:
    int data;
    Node* next;
};
 
// Function to add a node at the
// beginning of List
void push(Node** head_ref, int data) 
{ 
    /* allocate node */
    Node* new_node =new Node();
   
    /* put in the data */
    new_node->data = data; 
   
    // link the old list off the new
    // node
    new_node->next = (*head_ref); 
   
    // move the head to point to the
    // new node
    (*head_ref) = new_node; 
}
 
 
// Counts the no. of occurrences of a
// node in a linked list
int countValuesWithSameFreq(Node* start)
{
    map<int, int> mpp;
    Node* current = start;
    int count = 0;
    while (current != NULL) {
        mpp[current->data] += 1;
        current = current->next;
    }
    int ans = 0;
    for (auto x : mpp) {
        int value = x.first;
        int freq = x.second;
 
        // Check if value equals to frequency
        // and increment the count
        if (value == freq) {
            ans++;
        }
    }
    return ans;
}
 
// main program
int main()
{
    Node* head = NULL;
    push(&head, 3);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 2);
    push(&head, 3);
 
    cout << countValuesWithSameFreq(head);
    return 0;
}

/* Link list node */
import java.util.*;
 
class GFG{
 
public static class Node
{
    int data;
    Node next;
};
 
// Function to add a node at the
// beginning of List
static Node push(Node head_ref, int data)
{
     
    // Allocate node
    Node new_node = new Node();
 
    // Put in the data
    new_node.data = data;
 
    // Link the old list off the new
    // node
    new_node.next = head_ref;
 
    // Move the head to point to the
    // new node
    head_ref = new_node;
    return head_ref;
}
 
// Counts the no. of occurrences of a
// node in a linked list
static int countValuesWithSameFreq(Node start)
{
    HashMap<Integer, Integer> mpp = new HashMap<>();
     
    Node current = start;
    while (current != null)
    {
        if (mpp.containsKey(current.data))
        {
            mpp.put(current.data,
                     mpp.get(current.data) + 1);
        }
        else
        {
            mpp.put(current.data, 1);
        }
        current = current.next;
    }
    int ans = 0;
    for(Map.Entry<Integer,
                  Integer> x : mpp.entrySet())
    {
        int value = x.getKey();
        int freq = x.getValue();
 
        // Check if value equals to frequency
        // and increment the count
        if (value == freq)
        {
            ans++;
        }
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    Node head = null;
    head = push(head, 3);
    head = push(head, 4);
    head = push(head, 3);
    head = push(head, 2);
    head = push(head, 2);
    head = push(head, 3);
 
    System.out.print(countValuesWithSameFreq(head));
}
}
 
// This code is contributed by amal kumar choubey

# Link list node
class Node:
     
    def __init(self, next):
         
        self.data = 0
        self.next = None
  
# Function to add a node at the
# beginning of List
def push(head_ref, data):
     
    # Allocate node
    new_node = Node()
     
    # Put in the data
    new_node.data = data
    
    # Link the old list off the new
    # node
    new_node.next = (head_ref) 
    
    # Move the head to point to the
    # new node
    (head_ref) = new_node
     
    return head_ref
     
# Counts the no. of occurrences of a
# node in a linked list
def countValuesWithSameFreq(start):
     
    mpp = dict()
    current = start
    count = 0
     
    while (current != None):
        if current.data not in mpp:
            mpp[current.data] = 0
             
        mpp[current.data] += 1
        current = current.next
     
    ans = 0
     
    for x in mpp.keys():
        value = x
        freq = mpp[x]
         
        # Check if value equals to frequency
        # and increment the count
        if (value == freq):
            ans += 1
             
    return ans
  
# Driver code
if __name__=='__main__':
     
    head = None
    head = push(head, 3)
    head = push(head, 4)
    head = push(head, 3)
    head = push(head, 2)
    head = push(head, 2)
    head = push(head, 3)
  
    print(countValuesWithSameFreq(head))
     
# This code is contributed by rutvik_56

/* Link list node */
using System;
using System.Collections.Generic;
 
class GFG{
 
public class Node
{
    public int data;
    public Node next;
};
 
// Function to add a node at the
// beginning of List
static Node push(Node head_ref, int data)
{
     
    // Allocate node
    Node new_node = new Node();
 
    // Put in the data
    new_node.data = data;
 
    // Link the old list off the new
    // node
    new_node.next = head_ref;
 
    // Move the head to point to the
    // new node
    head_ref = new_node;
    return head_ref;
}
 
// Counts the no. of occurrences of a
// node in a linked list
static int countValuesWithSameFreq(Node start)
{
    Dictionary<int,
                 int> mpp = new Dictionary<int,
                                           int>();
     
    Node current = start;
    while (current != null)
    {
        if (mpp.ContainsKey(current.data))
        {
            mpp[current.data] = mpp[current.data] + 1;
        }
        else
        {
            mpp.Add(current.data, 1);
        }
        current = current.next;
    }
    int ans = 0;
     
    foreach(KeyValuePair<int, int> x in mpp)
    {
        int value = x.Key;
        int freq = x.Value;
 
        // Check if value equals to frequency
        // and increment the count
        if (value == freq)
        {
            ans++;
        }
    }
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    Node head = null;
    head = push(head, 3);
    head = push(head, 4);
    head = push(head, 3);
    head = push(head, 2);
    head = push(head, 2);
    head = push(head, 3);
 
    Console.Write(countValuesWithSameFreq(head));
}
}
 
// This code is contributed by Rohit_ranjan

<script>
 
/* Link list node */
 
class Node
{
    constructor()
    {
        this.data = 0;
        this.next = null;
    }
};
 
// Function to add a node at the
// beginning of List
function push(head_ref, data)
{
     
    // Allocate node
    var new_node = new Node();
 
    // Put in the data
    new_node.data = data;
 
    // Link the old list off the new
    // node
    new_node.next = head_ref;
 
    // Move the head to point to the
    // new node
    head_ref = new_node;
    return head_ref;
}
 
// Counts the no. of occurrences of a
// node in a linked list
function countValuesWithSameFreq(start)
{
    var mpp = new Map();
     
    var current = start;
    while (current != null)
    {
        if (mpp.has(current.data))
        {
            mpp.set(current.data , mpp.get(current.data)+1);
        }
        else
        {
            mpp.set(current.data, 1);
        }
        current = current.next;
    }
    var ans = 0;
     
    mpp.forEach((value, key) => {
        var value = value;
        var freq = key;
 
        // Check if value equals to frequency
        // and increment the count
        if (value == freq)
        {
            ans++;
        }
    });
    return ans;
}
 
// Driver code
var head = null;
head = push(head, 3);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 2);
head = push(head, 3);
document.write(countValuesWithSameFreq(head));
 
</script>

Producción: 

2

Análisis de  
Complejidad: Complejidad de Tiempo: Para una lista enlazada dada de tamaño n , estamos iterando sobre ella una vez. Entonces, la complejidad temporal de esta solución es O(n)  
Complejidad espacial: para una lista enlazada dada de tamaño n , estamos usando un mapa adicional que puede tener un máximo de n valores-clave, por lo que la complejidad espacial de esta solución es O(n )