Dada una lista enlazada, la tarea es encontrar la suma de todos los Nodes de frecuencias impares de la lista enlazada dada.
Ejemplos:
Entrada: 8 -> 8 -> 1 -> 4 -> 1 -> 2 -> 8 -> NULL
Salida: 30
frecuencia(8) = 3
frecuencia(1) = 2
frecuencia(4) = 1
frecuencia(2) = 1
8, 4 y 2 aparecen un número impar de veces y (8 * 3) + (4 * 1) + (2 * 1) = 30
Entrada: 6 -> 2 -> 2 -> 6 -> 2 -> 1 – >
Salida NULA: 7
Enfoque: este problema se puede resolver mediante hash ,
- Crea un hash para almacenar las frecuencias de los Nodes.
- Recorra la lista enlazada y actualice las frecuencias de los Nodes en la variable hash.
- Ahora, recorra la lista enlazada nuevamente y para cada Node que aparezca un número impar de veces, agregue su valor a la suma acumulada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include<bits/stdc++.h>
using namespace std;
// Node class
struct Node
{
int data;
Node* next;
Node(int d)
{
data = d;
next = NULL;
}
} ;
// Function to push the new node
// to head of the linked list
Node* push(Node* head,int data)
{
// If head is null return new node as head
if (!head)
return new Node(data);
Node* temp =new Node(data);
temp->next = head;
head = temp;
return head;
}
// Function to find the sum of all odd
// frequency nodes of the linked list
int sumOfOddFreqEle(Node* head)
{
// Hash to store the frequencies of
// the nodes of the linked list
map<int,int> mp ;
Node* temp = head;
while(temp)
{
int d = temp->data;
mp[d]++;
temp = temp->next;
}
// Initialize total_sum as zero
int total_sum = 0;
// Traverse through the map to get the sum
for (auto i : mp)
{
// If it appears for odd number of
// times then add it to the sum
if (i.second % 2 == 1)
total_sum+=(i.second * i.first);
}
return total_sum;
}
// Driver code
int main()
{
Node* head = NULL;
head = push(head, 8);
head = push(head, 2);
head = push(head, 1);
head = push(head, 4);
head = push(head, 1);
head = push(head, 8);
head = push(head, 8);
cout<<(sumOfOddFreqEle(head));
return 0;
}
// This code is contributed by Arnab Kundu
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Node class
static class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
};
// Function to push the new node
// to head of the linked list
static Node push(Node head,int data)
{
// If head is null return new node as head
if (head == null)
return new Node(data);
Node temp = new Node(data);
temp.next = head;
head = temp;
return head;
}
// Function to find the sum of all odd
// frequency nodes of the linked list
static int sumOfOddFreqEle(Node head)
{
// Hash to store the frequencies of
// the nodes of the linked list
HashMap<Integer, Integer> mp =
new HashMap<Integer, Integer>();
Node temp = head;
while(temp != null)
{
int d = temp.data;
if(mp.containsKey(d))
{
mp.put(d, mp.get(d) + 1);
}
else
{
mp.put(d, 1);
}
temp = temp.next;
}
// Initialize total_sum as zero
int total_sum = 0;
// Traverse through the map to get the sum
for (Map.Entry<Integer,
Integer> i : mp.entrySet())
{
// If it appears for odd number of
// times then add it to the sum
if (i.getValue() % 2 == 1)
total_sum+=(i.getValue() * i.getKey());
}
return total_sum;
}
// Driver code
public static void main(String[] args)
{
Node head = null;
head = push(head, 8);
head = push(head, 2);
head = push(head, 1);
head = push(head, 4);
head = push(head, 1);
head = push(head, 8);
head = push(head, 8);
System.out.println((sumOfOddFreqEle(head)));
}
}
// This code is contributed by Rajput-Ji
Python
# Python implementation of the approach
# Node class
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to push the new node
# to head of the linked list
def push(head, data):
# If head is null return new node as head
if not head:
return Node(data)
temp = Node(data)
temp.next = head
head = temp
return head
# Function to find the sum of all odd
# frequency nodes of the linked list
def sumOfOddFreqEle(head):
# Hash to store the frequencies of
# the nodes of the linked list
mp ={}
temp = head
while(temp):
d = temp.data
if d in mp:
mp[d]= mp.get(d)+1
else:
mp[d]= 1
temp = temp.next
# Initialize total_sum as zero
total_sum = 0
# Traverse through the map to get the sum
for digit in mp:
# keep tracking the to
tms = mp.get(digit)
# If it appears for odd number of
# times then add it to the sum
if tms % 2 == 1:
total_sum+=(tms * digit)
return total_sum
# Driver code
if __name__=='__main__':
head = None
head = push(head, 8)
head = push(head, 2)
head = push(head, 1)
head = push(head, 4)
head = push(head, 1)
head = push(head, 8)
head = push(head, 8)
print(sumOfOddFreqEle(head))
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Node class
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
};
// Function to push the new node
// to head of the linked list
static Node push(Node head,int data)
{
// If head is null,
// return new node as head
if (head == null)
return new Node(data);
Node temp = new Node(data);
temp.next = head;
head = temp;
return head;
}
// Function to find the sum of all odd
// frequency nodes of the linked list
static int sumOfOddFreqEle(Node head)
{
// Hash to store the frequencies of
// the nodes of the linked list
Dictionary<int,
int> mp = new Dictionary<int,
int>();
Node temp = head;
while(temp != null)
{
int d = temp.data;
if(mp.ContainsKey(d))
{
mp[d] = mp[d] + 1;
}
else
{
mp.Add(d, 1);
}
temp = temp.next;
}
// Initialize total_sum as zero
int total_sum = 0;
// Traverse through the map to get the sum
foreach(KeyValuePair<int, int> i in mp)
{
// If it appears for odd number of
// times then add it to the sum
if (i.Value % 2 == 1)
total_sum += (i.Value * i.Key);
}
return total_sum;
}
// Driver code
public static void Main(String[] args)
{
Node head = null;
head = push(head, 8);
head = push(head, 2);
head = push(head, 1);
head = push(head, 4);
head = push(head, 1);
head = push(head, 8);
head = push(head, 8);
Console.WriteLine((sumOfOddFreqEle(head)));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
// Node class
class Node {
constructor(d) {
this.data = d;
this.next = null;
}
}
// Function to push the new node
// to head of the linked list
function push(head, data) {
// If head is null,
// return new node as head
if (head == null) return new Node(data);
var temp = new Node(data);
temp.next = head;
head = temp;
return head;
}
// Function to find the sum of all odd
// frequency nodes of the linked list
function sumOfOddFreqEle(head) {
// Hash to store the frequencies of
// the nodes of the linked list
var mp = {};
var temp = head;
while (temp != null) {
var d = temp.data;
if (mp.hasOwnProperty(d)) {
mp[d] = mp[d] + 1;
} else {
mp[d] = 1;
}
temp = temp.next;
}
// Initialize total_sum as zero
var total_sum = 0;
// Traverse through the map to get the sum
for (const [key, value] of Object.entries(mp)) {
// If it appears for odd number of
// times then add it to the sum
if (value % 2 == 1) total_sum += value * key;
}
return total_sum;
}
// Driver code
var head = null;
head = push(head, 8);
head = push(head, 2);
head = push(head, 1);
head = push(head, 4);
head = push(head, 1);
head = push(head, 8);
head = push(head, 8);
document.write(sumOfOddFreqEle(head) + "<br>");
</script>
Producción:
30
Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Vikash Kumar 37 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA