Dada una lista enlazada. Necesitamos encontrar elementos únicos en la lista enlazada, es decir, aquellos elementos que no se repiten en la lista enlazada o aquellos elementos cuya frecuencia es 1. Si no hay tales elementos presentes en la lista, imprima «No hay elementos únicos».
Ejemplos:
Input : 1 -> 4 -> 4 -> 2 -> 3 -> 5 -> 3 -> 4 -> 5 Output :1 2 Input :4 -> 5 -> 2 -> 5 -> 1 -> 4 -> 1 -> 2 Output :No Unique Elements
Método 1 (Uso de dos bucles) Esta es la forma sencilla en la que se utilizan dos bucles. El bucle externo se usa para seleccionar los elementos uno por uno y el bucle interno compara el elemento seleccionado con el resto de los elementos. Si el elemento no es igual a otros elementos, imprima ese elemento. Complejidad de tiempo: O(N * n)
Método 2 (Clasificación): Ordene los elementos usando Merge Sort. O(n Registro n). Ahora Traverse List en tiempo lineal y verifique si el elemento actual no es igual al elemento anterior, luego imprima O (N)
Tenga en cuenta que este método no conserva el orden original de los elementos.
Complejidad de tiempo: O(NLogN)
Método 3 (Hashing)
Usamos el concepto de tabla Hash Aquí, recorremos la lista de enlaces de principio a fin. Para cada elemento recién encontrado, lo colocamos en la tabla hash, luego de eso, nuevamente recorremos la lista e imprimimos aquellos elementos cuya frecuencia es 1. Complejidad de tiempo: O (N)
A continuación se muestra la implementación de esto
C++
// C++ Program to Find the Unique elements in
// linked lists
#include <bits/stdc++.h>
using namespace std;
/* Linked list node */
struct Node {
int data;
struct Node* next;
};
/* Function to insert a node at the beginning of
the linked list */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
// function to Find the unique elements in linked lists
void uniqueElements(struct Node* head)
{
// Initialize hash array that store the
// frequency of each element of list
unordered_map<int, int> hash;
for (Node *temp=head; temp!=NULL; temp=temp->next)
hash[temp->data]++;
int count = 0;
for (Node *temp=head; temp!=NULL; temp=temp->next) {
// Check whether the frequency of current
// element is 1 or not
if (hash[temp->data] == 1) {
cout << temp->data << " ";
count++;
}
}
// If No unique element in list
if (count == 0)
cout << " No Unique Elements ";
}
// Driver program to test above
int main()
{
struct Node* head = NULL;
// creating linked list
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 5);
push(&head, 3);
push(&head, 2);
push(&head, 4);
push(&head, 4);
push(&head, 1);
uniqueElements(head);
return 0;
}
Java
// Java Program to Find the Unique elements
// in linked lists
import java.util.*;
class GFG
{
/* Linked list node */
static class Node
{
int data;
Node next;
};
static Node head;
/* Function to insert a node at the
beginning of the linked list */
static void push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head = head_ref;
}
// function to Find the unique elements
// in linked lists
static void uniqueElements(Node head)
{
// Initialize hash array that store the
// frequency of each element of list
HashMap<Integer,
Integer> hash = new HashMap<Integer,
Integer>();
for (Node temp = head;
temp != null; temp = temp.next)
{
if(hash.containsKey(temp.data))
{
hash.put(temp.data,
hash.get(temp.data) + 1);
}
else
{
hash.put(temp.data, 1);
}
}
int count = 0;
for (Node temp = head;
temp != null; temp = temp.next)
{
// Check whether the frequency of current
// element is 1 or not
if (hash.get(temp.data) == 1)
{
System.out.print(temp.data + " ");
count++;
}
}
// If No unique element in list
if (count == 0)
System.out.print(" No Unique Elements ");
}
// Driver Code
public static void main(String[] args)
{
head = null;
// creating linked list
push(head, 5);
push(head, 4);
push(head, 3);
push(head, 5);
push(head, 3);
push(head, 2);
push(head, 4);
push(head, 4);
push(head, 1);
uniqueElements(head);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 Program to Find the Unique elements in
# linked lists
import sys
import math
# Linked list node
class Node:
def __init__(self,data):
self.data = data
self.next = None
# Function to insert a node at the beginning of
# the linked list
def push(head,data):
if not head:
return Node(data)
temp = Node(data)
temp.next = head
head = temp
return head
# function to Find the unique elements in linked lists
def uniqueElements(head):
# Initialize hash array that store the
# frequency of each element of list
_map = {}
temp = head
while(temp):
d = temp.data
if d in _map:
_map[d]=_map.get(d)+1
else:
_map[d] = 1
temp = temp.next
count = 0
for i in _map:
# Check whether the frequency of current
# element is 1 or not
if _map.get(i) == 1:
count += 1
print("{} ".format(i),end="")
# If No unique element in list
if count == 0:
print("No Unique Elements")
# Driver program to test above
if __name__=='__main__':
# creating linked list
head = None
head = push(head,5)
head = push(head,4)
head = push(head,3)
head = push(head,5)
head = push(head,3)
head = push(head,2)
head = push(head,4)
head = push(head,4)
head = push(head,1)
uniqueElements(head)
# This code is Contributed by Vikash Kumar 37
C#
// C# Program to Find the Unique elements
// in linked lists
using System;
using System.Collections.Generic;
class GFG
{
/* Linked list node */
public class Node
{
public int data;
public Node next;
};
static Node head;
/* Function to insert a node at the
beginning of the linked list */
static void push(Node head_ref,
int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head = head_ref;
}
// function to Find the unique elements
// in linked lists
static void uniqueElements(Node head)
{
// Initialize hash array that store the
// frequency of each element of list
Dictionary<int,
int> hash = new Dictionary<int,
int>();
for (Node temp = head;
temp != null; temp = temp.next)
{
if(hash.ContainsKey(temp.data))
{
hash[temp.data] = hash[temp.data] + 1;
}
else
{
hash.Add(temp.data, 1);
}
}
int count = 0;
for (Node temp = head;
temp != null; temp = temp.next)
{
// Check whether the frequency of
// current element is 1 or not
if (hash[temp.data] == 1)
{
Console.Write(temp.data + " ");
count++;
}
}
// If No unique element in list
if (count == 0)
Console.Write(" No Unique Elements ");
}
// Driver Code
public static void Main(String[] args)
{
head = null;
// creating linked list
push(head, 5);
push(head, 4);
push(head, 3);
push(head, 5);
push(head, 3);
push(head, 2);
push(head, 4);
push(head, 4);
push(head, 1);
uniqueElements(head);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript Program to Find the Unique elements
// in linked lists
/* Linked list node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
var head = null;
/* Function to insert a node at the
beginning of the linked list */
function push(head_ref, new_data) {
var new_node = new Node();
new_node.data = new_data;
new_node.next = head_ref;
head_ref = new_node;
head = head_ref;
}
// function to Find the unique elements
// in linked lists
function uniqueElements(head) {
// Initialize hash array that store the
// frequency of each element of list
var hash = {};
for (var temp = head; temp != null; temp = temp.next) {
if (hash.hasOwnProperty(temp.data)) {
hash[temp.data] = hash[temp.data] + 1;
} else {
hash[temp.data] = 1;
}
}
var count = 0;
for (var temp = head; temp != null; temp = temp.next) {
// Check whether the frequency of
// current element is 1 or not
if (hash[temp.data] == 1) {
document.write(temp.data + " ");
count++;
}
}
// If No unique element in list
if (count == 0) document.write(" No Unique Elements ");
}
// Driver Code
head = null;
// creating linked list
push(head, 5);
push(head, 4);
push(head, 3);
push(head, 5);
push(head, 3);
push(head, 2);
push(head, 4);
push(head, 4);
push(head, 1);
uniqueElements(head);
// This code is contributed by rdtank.
</script>
Producción:
1 2
Tiempo Complejidad : O(N)
Espacio Auxiliar : O(N)