Dada una Lista Vinculada que consta de números enteros, la tarea es imprimir el número de valores absolutos distintos presentes en la Lista Vinculada.
Ejemplos:
Entrada: -1 -> -2 -> 0 -> 4 -> 5 -> 8
Salida: 6
Explicación:
Los valores de Node absolutos distintos son {0, 1, 2, 4, 5, 8}Entrada: -1 -> -1 -> -1 -> 0 -> 1
Salida: 2
Explicación:
Los valores de Node absolutos distintos son {0, 1}.
Enfoque: Para resolver este problema, requerimos un Set o un HashSet para almacenar los distintos valores absolutos presentes en la Lista Enlazada. Después de recorrer toda la lista vinculada e insertar valores absolutos de cada Node en el Conjunto , el tamaño del Conjunto proporciona el número de valores distintos absolutos presentes en la Lista vinculada.
A continuación se muestra la implementación del enfoque:
C++
// C++ Program to print the count // of distinct absolute values // in a linked list #include <bits/stdc++.h> using namespace std; // Node of a singly // linked list struct Node { int data; Node* next; }; // Function to insert a // node at the beginning // of a singly Linked List void push(Node** head_ref, int new_data) { // Allocate node Node* new_node = new Node(); // Insert the data new_node->data = new_data; // Point to the current head new_node->next = (*head_ref); // Make the current Node // the new head (*head_ref) = new_node; } // Function to return number of // distinct absolute values // present in the linked list int distinctCount(Node* head_1) { Node* ptr = head_1; unordered_set<int> s; while (ptr != NULL) { s.insert(abs(ptr->data)); ptr = ptr->next; } return s.size(); } int main() { // Create the head Node* head1 = NULL; // Insert Nodes push(&head1, -1); push(&head1, -2); push(&head1, 0); push(&head1, 4); push(&head1, 5); push(&head1, 8); int k = distinctCount(head1); cout << k; return 0; }
Java
// Java program to calculate // the count of distinct // absolute values in a // linked list import java.util.*; class GFG { // Node of the singly // linked list static class Node { int data; Node next; }; // Function to insert a node // at the beginning of the // singly Linked List static Node push(Node head_ref, int new_data) { // Allocate node Node new_node = new Node(); // Insert the data new_node.data = new_data; // Point the current Node // to the current head new_node.next = (head_ref); // Make the current node // as the new head (head_ref) = new_node; return head_ref; } // Function to return the count of // distinct absolute values // present in the Linked list static int distinctCount(Node head_ref1) { Set<Integer> s = new HashSet<Integer>(); Node ptr1 = head_ref1; while (ptr1 != null) { s.add(Math.abs(ptr1.data)); ptr1 = ptr1.next; } return s.size(); } // Driver Code public static void main(String args[]) { // Create the head Node head1 = null; // Insert nodes to the // Linked List head1 = push(head1, -1); head1 = push(head1, -2); head1 = push(head1, 0); head1 = push(head1, 4); head1 = push(head1, 5); head1 = push(head1, 8); int ans = distinctCount(head1); System.out.println(ans); } }
Python3
# Python3 program to calculate # the count of distinct # absolute values in a # linked list class Node: def __init__(self, data): self.data = data self.next = next # Function to insert a # node at the beginning # of the singly Linked List def push( head_ref, new_data) : # Allocate node new_node = Node(0) # Insert data new_node.data = new_data # Point to the head new_node.next = (head_ref) # Make the new Node # the new head (head_ref) = new_node return head_ref # Function to return the # count of distinct absolute # values in the linked list def distinctCount(head_ref1): s = set() ptr1 = head_ref1 # set keeps all unique elements while (ptr1 != None): s.add(abs(ptr1.data)) ptr1 = ptr1.next return len(s) # Driver code # Create the Head head1 = None # Insert nodes head1 = push(head1, -1) head1 = push(head1, -2) head1 = push(head1, 0) head1 = push(head1, 4) head1 = push(head1, 5) head1 = push(head1, 8) ans = distinctCount(head1) print(ans)
C#
// C# program to calculate the count // of distinct absolute values in a // linked list using System; using System.Collections.Generic; class GFG{ // Node of the singly // linked list class Node { public int data; public Node next; }; // Function to insert a node // at the beginning of the // singly Linked List static Node push(Node head_ref, int new_data) { // Allocate node Node new_node = new Node(); // Insert the data new_node.data = new_data; // Point the current Node // to the current head new_node.next = (head_ref); // Make the current node // as the new head (head_ref) = new_node; return head_ref; } // Function to return the count of // distinct absolute values // present in the Linked list static int distinctCount(Node head_ref1) { HashSet<int> s = new HashSet<int>(); Node ptr1 = head_ref1; while (ptr1 != null) { s.Add(Math.Abs(ptr1.data)); ptr1 = ptr1.next; } return s.Count; } // Driver Code public static void Main(String []args) { // Create the head Node head1 = null; // Insert nodes to the // Linked List head1 = push(head1, -1); head1 = push(head1, -2); head1 = push(head1, 0); head1 = push(head1, 4); head1 = push(head1, 5); head1 = push(head1, 8); int ans = distinctCount(head1); Console.WriteLine(ans); } } // This code is contributed by Princi Singh
6
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar : O(N), ya que estamos usando espacio extra para el conjunto s.
Publicación traducida automáticamente
Artículo escrito por ShivaTeja2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA