Escriba una función removeDuplicates() que tome una lista y elimine cualquier Node duplicado de la lista. La lista no está ordenada.
Por ejemplo, si la lista vinculada es 12->11->12->21->41->43->21, removeDuplicates() debería convertir la lista a 12->11->21->41->43.
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.
Gracias a Gaurav Saxena por su ayuda al escribir este código.
C++
/* C++ Program to remove duplicates in an unsorted
linked list */
#include <bits/stdc++.h>
using namespace std;
/* A linked list node */
struct Node {
int data;
struct Node* next;
};
// Utility function to create a new Node
struct Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
/* Function to remove duplicates from a
unsorted linked list */
void removeDuplicates(struct Node* start)
{
struct Node *ptr1, *ptr2, *dup;
ptr1 = start;
/* Pick elements one by one */
while (ptr1 != NULL && ptr1->next != NULL) {
ptr2 = ptr1;
/* Compare the picked element with rest
of the elements */
while (ptr2->next != NULL) {
/* If duplicate then delete it */
if (ptr1->data == ptr2->next->data) {
/* sequence of steps is important here */
dup = ptr2->next;
ptr2->next = ptr2->next->next;
delete (dup);
}
else /* This is tricky */
ptr2 = ptr2->next;
}
ptr1 = ptr1->next;
}
}
/* Function to print nodes in a given linked list */
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
/* Driver program to test above function */
int main()
{
/* The constructed linked list is:
10->12->11->11->12->11->10*/
struct Node* start = newNode(10);
start->next = newNode(12);
start->next->next = newNode(11);
start->next->next->next = newNode(11);
start->next->next->next->next = newNode(12);
start->next->next->next->next->next = newNode(11);
start->next->next->next->next->next->next = newNode(10);
printf("Linked list before removing duplicates ");
printList(start);
removeDuplicates(start);
printf("\nLinked list after removing duplicates ");
printList(start);
return 0;
}
Java
// Java program to remove duplicates from unsorted
// linked list
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Function to remove duplicates from an
unsorted linked list */
void remove_duplicates()
{
Node ptr1 = null, ptr2 = null, dup = null;
ptr1 = head;
/* Pick elements one by one */
while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;
/* Compare the picked element with rest
of the elements */
while (ptr2.next != null) {
/* If duplicate then delete it */
if (ptr1.data == ptr2.next.data) {
/* sequence of steps is important here
*/
ptr2.next = ptr2.next.next;
System.gc();
}
else /* This is tricky */ {
ptr2 = ptr2.next;
}
}
ptr1 = ptr1.next;
}
}
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(10);
list.head.next = new Node(12);
list.head.next.next = new Node(11);
list.head.next.next.next = new Node(11);
list.head.next.next.next.next = new Node(12);
list.head.next.next.next.next.next = new Node(11);
list.head.next.next.next.next.next.next
= new Node(10);
System.out.println(
"Linked List before removing duplicates : \n ");
list.printList(head);
list.remove_duplicates();
System.out.println("");
System.out.println(
"Linked List after removing duplicates : \n ");
list.printList(head);
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Python3 program to remove duplicates
# from unsorted linked list
class Node():
def __init__(self, data):
self.data = data
self.next = None
class LinkedList():
def __init__(self):
# Head of list
self.head = None
def remove_duplicates(self):
ptr1 = None
ptr2 = None
dup = None
ptr1 = self.head
# Pick elements one by one
while (ptr1 != None and ptr1.next != None):
ptr2 = ptr1
# Compare the picked element with rest
# of the elements
while (ptr2.next != None):
# If duplicate then delete it
if (ptr1.data == ptr2.next.data):
# Sequence of steps is important here
dup = ptr2.next
ptr2.next = ptr2.next.next
else:
ptr2 = ptr2.next
ptr1 = ptr1.next
# Function to print nodes in a
# given linked list
def printList(self):
temp = self.head
while(temp != None):
print(temp.data, end=" ")
temp = temp.next
print()
# Driver code
list = LinkedList()
list.head = Node(10)
list.head.next = Node(12)
list.head.next.next = Node(11)
list.head.next.next.next = Node(11)
list.head.next.next.next.next = Node(12)
list.head.next.next.next.next.next = Node(11)
list.head.next.next.next.next.next.next = Node(10)
print("Linked List before removing duplicates :")
list.printList()
list.remove_duplicates()
print()
print("Linked List after removing duplicates :")
list.printList()
# This code is contributed by maheshwaripiyush9
C#
// C# program to remove duplicates from unsorted
// linked list
using System;
class List_ {
Node head;
class Node {
public int data;
public Node next;
public
Node(int d)
{
data = d;
next = null;
}
}
/* Function to remove duplicates from an
unsorted linked list */
void remove_duplicates()
{
Node ptr1 = null, ptr2 = null, dup = null;
ptr1 = head;
/* Pick elements one by one */
while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;
/* Compare the picked element with rest
of the elements */
while (ptr2.next != null) {
/* If duplicate then delete it */
if (ptr1.data == ptr2.next.data) {
/* sequence of steps is important here
*/
dup = ptr2.next;
ptr2.next = ptr2.next.next;
}
else /* This is tricky */
{
ptr2 = ptr2.next;
}
}
ptr1 = ptr1.next;
}
}
void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
// Driver Code
public static void Main(String[] args)
{
List_ list = new List_();
list.head = new Node(10);
list.head.next = new Node(12);
list.head.next.next = new Node(11);
list.head.next.next.next = new Node(11);
list.head.next.next.next.next = new Node(12);
list.head.next.next.next.next.next = new Node(11);
list.head.next.next.next.next.next.next
= new Node(10);
Console.WriteLine(
"Linked List_ before removing duplicates : \n ");
list.printList(list.head);
list.remove_duplicates();
Console.WriteLine("");
Console.WriteLine(
"Linked List_ after removing duplicates : \n ");
list.printList(list.head);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// javascript program to remove duplicates from unsorted
// linked list
var head;
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
/*
* Function to remove duplicates from an unsorted linked list
*/
function remove_duplicates() {
var ptr1 = null, ptr2 = null, dup = null;
ptr1 = head;
/* Pick elements one by one */
while (ptr1 != null && ptr1.next != null) {
ptr2 = ptr1;
/*
* Compare the picked element with rest of the elements
*/
while (ptr2.next != null) {
/* If duplicate then delete it */
if (ptr1.data == ptr2.next.data) {
/* sequence of steps is important here */
dup = ptr2.next;
ptr2.next = ptr2.next.next;
} else /* This is tricky */ {
ptr2 = ptr2.next;
}
}
ptr1 = ptr1.next;
}
}
function printList( node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
head = new Node(10);
head.next = new Node(12);
head.next.next = new Node(11);
head.next.next.next = new Node(11);
head.next.next.next.next = new Node(12);
head.next.next.next.next.next = new Node(11);
head.next.next.next.next.next.next = new Node(10);
document.write("Linked List before removing duplicates : <br/> ");
printList(head);
remove_duplicates();
document.write("<br/>");
document.write("Linked List after removing duplicates : <br/> ");
printList(head);
// This code contributed by aashish1995
</script>
Producción
Linked list before removing duplicates 10 12 11 11 12 11 10 Linked list after removing duplicates 10 12 11
Complejidad de tiempo : O (n ^ 2)
Espacio Auxiliar: O(1)
MÉTODO 2 (Uso de clasificación)
En general, Merge Sort es el algoritmo de clasificación más adecuado para clasificar listas vinculadas de manera eficiente.
1) Ordenar los elementos usando Merge Sort. Pronto escribiremos una publicación sobre cómo ordenar una lista enlazada. O(nLogn)
2) Eliminar duplicados en tiempo lineal utilizando el algoritmo para eliminar duplicados en Lista enlazada ordenada. 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 (Usar Hashing) Recorremos
la lista de enlaces de principio a fin. Para cada elemento recién encontrado, verificamos si está en la tabla hash: si es así, lo eliminamos; de lo contrario, lo ponemos en la tabla hash.
C++
/* C++ Program to remove duplicates in an unsorted
linked list */
#include <bits/stdc++.h>
using namespace std;
/* A linked list node */
struct Node {
int data;
struct Node* next;
};
// Utility function to create a new Node
struct Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
/* Function to remove duplicates from a
unsorted linked list */
void removeDuplicates(struct Node* start)
{
// Hash to store seen values
unordered_set<int> seen;
/* Pick elements one by one */
struct Node* curr = start;
struct Node* prev = NULL;
while (curr != NULL) {
// If current value is seen before
if (seen.find(curr->data) != seen.end()) {
prev->next = curr->next;
delete (curr);
}
else {
seen.insert(curr->data);
prev = curr;
}
curr = prev->next;
}
}
/* Function to print nodes in a given linked list */
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
/* Driver program to test above function */
int main()
{
/* The constructed linked list is:
10->12->11->11->12->11->10*/
struct Node* start = newNode(10);
start->next = newNode(12);
start->next->next = newNode(11);
start->next->next->next = newNode(11);
start->next->next->next->next = newNode(12);
start->next->next->next->next->next = newNode(11);
start->next->next->next->next->next->next = newNode(10);
printf("Linked list before removing duplicates : \n");
printList(start);
removeDuplicates(start);
printf("\nLinked list after removing duplicates : \n");
printList(start);
return 0;
}
Java
// Java program to remove duplicates
// from unsorted linkedlist
import java.util.HashSet;
public class removeDuplicates {
static class node {
int val;
node next;
public node(int val) { this.val = val; }
}
/* Function to remove duplicates from a
unsorted linked list */
static void removeDuplicate(node head)
{
// Hash to store seen values
HashSet<Integer> hs = new HashSet<>();
/* Pick elements one by one */
node current = head;
node prev = null;
while (current != null) {
int curval = current.val;
// If current value is seen before
if (hs.contains(curval)) {
prev.next = current.next;
}
else {
hs.add(curval);
prev = current;
}
current = current.next;
}
}
/* Function to print nodes in a given linked list */
static void printList(node head)
{
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
}
public static void main(String[] args)
{
/* The constructed linked list is:
10->12->11->11->12->11->10*/
node start = new node(10);
start.next = new node(12);
start.next.next = new node(11);
start.next.next.next = new node(11);
start.next.next.next.next = new node(12);
start.next.next.next.next.next = new node(11);
start.next.next.next.next.next.next = new node(10);
System.out.println(
"Linked list before removing duplicates :");
printList(start);
removeDuplicate(start);
System.out.println(
"\nLinked list after removing duplicates :");
printList(start);
}
}
// This code is contributed by Rishabh Mahrsee
Python3
# Python3 program to remove duplicates
# from unsorted linkedlist
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# Function to print nodes in a
# given linked list
def printlist(self):
temp = self.head
while (temp):
print(temp.data, end=" ")
temp = temp.next
# Function to remove duplicates from a
# unsorted linked list
def removeDuplicates(self, head):
# Base case of empty list or
# list with only one element
if self.head is None or self.head.next is None:
return head
# Hash to store seen values
hash = set()
current = head
hash.add(self.head.data)
while current.next is not None:
if current.next.data in hash:
current.next = current.next.next
else:
hash.add(current.next.data)
current = current.next
return head
# Driver code
if __name__ == "__main__":
# Creating Empty list
llist = LinkedList()
llist.head = Node(10)
second = Node(12)
third = Node(11)
fourth = Node(11)
fifth = Node(12)
sixth = Node(11)
seventh = Node(10)
# Connecting second and third
llist.head.next = second
second.next = third
third.next = fourth
fourth.next = fifth
fifth.next = sixth
sixth.next = seventh
# Printing data
print("Linked List before removing Duplicates.")
llist.printlist()
llist.removeDuplicates(llist.head)
print("\nLinked List after removing duplicates.")
llist.printlist()
# This code is contributed by rajataro0
C#
// C# program to remove duplicates
// from unsorted linkedlist
using System;
using System.Collections.Generic;
class removeDuplicates {
class node {
public int val;
public node next;
public node(int val) { this.val = val; }
}
// Function to remove duplicates from a
// unsorted linked list
static void removeDuplicate(node head)
{
// Hash to store seen values
HashSet<int> hs = new HashSet<int>();
// Pick elements one by one
node current = head;
node prev = null;
while (current != null) {
int curval = current.val;
// If current value is seen before
if (hs.Contains(curval)) {
prev.next = current.next;
}
else {
hs.Add(curval);
prev = current;
}
current = current.next;
}
}
// Function to print nodes in a
// given linked list
static void printList(node head)
{
while (head != null) {
Console.Write(head.val + " ");
head = head.next;
}
}
// Driver code
public static void Main(String[] args)
{
// The constructed linked list is:
// 10->12->11->11->12->11->10
node start = new node(10);
start.next = new node(12);
start.next.next = new node(11);
start.next.next.next = new node(11);
start.next.next.next.next = new node(12);
start.next.next.next.next.next = new node(11);
start.next.next.next.next.next.next = new node(10);
Console.WriteLine("Linked list before removing "
+ "duplicates :");
printList(start);
removeDuplicate(start);
Console.WriteLine("\nLinked list after removing "
+ "duplicates :");
printList(start);
}
}
// This code is contributed by amal kumar choubey
Javascript
<script>
// JavaScript program to remove duplicates
// from unsorted linkedlist
class node {
constructor(val) {
this.val = val;
this.next = null;
}
}
/*
Function to remove duplicates
from a unsorted linked list
*/
function removeDuplicate( head) {
// Hash to store seen values
var hs = new Set();
/* Pick elements one by one */
var current = head;
var prev = null;
while (current != null) {
var curval = current.val;
// If current value is seen before
if (hs.has(curval)) {
prev.next = current.next;
} else {
hs.add(curval);
prev = current;
}
current = current.next;
}
}
/* Function to print nodes in a
given linked list */
function printList( head) {
while (head != null) {
document.write(head.val + " ");
head = head.next;
}
}
/*
* The constructed linked list is:
10->12->11->11->12->11->10
*/
start = new node(10);
start.next = new node(12);
start.next.next = new node(11);
start.next.next.next = new node(11);
start.next.next.next.next = new node(12);
start.next.next.next.next.next = new node(11);
start.next.next.next.next.next.next = new node(10);
document.write(
"Linked list before removing duplicates :<br/>"
);
printList(start);
removeDuplicate(start);
document.write(
"<br/>Linked list after removing duplicates :<br/>"
);
printList(start);
// This code is contributed by todaysgaurav
</script>
Producción
Linked list before removing duplicates : 10 12 11 11 12 11 10 Linked list after removing duplicates : 10 12 11
Gracias a bearwang por sugerir este método.
Complejidad de tiempo: O(N) en promedio
(suponiendo que el tiempo de acceso a la tabla hash es O (1) en promedio).
Espacio Auxiliar : O(N)
Como espacio adicional se utiliza para almacenar los elementos en la pila.
Escriba comentarios si encuentra alguna de las explicaciones/algoritmos anteriores incorrectos, o una mejor manera de resolver el mismo problema.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA