Recuento distinto absoluto en una lista vinculada

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++ 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 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 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# 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.