Escriba una función removeDuplicates() que tome una lista ordenada en orden no decreciente y elimine cualquier Node duplicado de la lista. La lista solo debe recorrerse una vez.
Por ejemplo, si la lista vinculada es 11->11->11->21->43->43->60, removeDuplicates() debería convertir la lista a 11->21->43->60.
Algoritmo:
recorre la lista de forma recursiva desde el principio (o el inicio) hasta el final y, después de completar las llamadas de recursión, compara el siguiente Node (Node devuelto) y el Node actual (principal). Si los datos de ambos Nodes son iguales, devuelva el siguiente (cabeza-> siguiente) Node; de lo contrario, devuelva el Node actual (cabeza) .
Implementación:
las funciones que no sean removeDuplicates() son solo para crear una lista vinculada y probar removeDuplicates().
C++
/* C Program to remove duplicates
from a sorted linked list */
#include <bits/stdc++.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* The function removes duplicates from a sorted list */
struct Node* removeDuplicates(struct Node* head)
{
/* if head is null then return*/
if (head == NULL)
return NULL;
/* Remove duplicates from list after head */
head->next = removeDuplicates(head->next);
// Check if head itself is duplicate
if (head->next != NULL &&
head->next->data == head->data) {
Node* res = head->next;
delete head;
return res;
}
return head;
}
/* UTILITY FUNCTIONS */
/* 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 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 functions*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Let us create a sorted linked list to test the functions
Created linked list will be 11->11->11->13->13->20 */
push(&head, 20);
push(&head, 13);
push(&head, 13);
push(&head, 11);
push(&head, 11);
push(&head, 11);
printf("\n Linked list before duplicate removal ");
printList(head);
/* Remove duplicates from linked list */
struct Node* h = removeDuplicates(head);
printf("\n Linked list after duplicate removal ");
printList(h);
return 0;
}
Java
/* Java Program to remove duplicates
from a sorted linked list */
class GFG
{
/* Link list node */
static class Node
{
int data;
Node next;
};
/* The function removes duplicates from a sorted list */
static Node removeDuplicates( Node head)
{
/* if head is null then return*/
if (head == null)
return null;
/* Remove duplicates from list after head */
head.next = removeDuplicates(head.next);
// Check if head itself is duplicate
if (head.next != null &&
head.next.data == head.data)
{
Node res = head.next;
return res;
}
return head;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at
the beginning of the linked list */
static Node 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;
return head_ref;
}
/* Function to print nodes in a given linked list */
static void printList( Node node)
{
while (node != null)
{
System.out.printf("%d ", node.data);
node = node.next;
}
}
/* Driver program to test above functions*/
public static void main(String args[])
{
/* Start with the empty list */
Node head = null;
/* Let us create a sorted linked list to test the functions
Created linked list will be 11.11.11.13.13.20 */
head = push(head, 20);
head = push(head, 13);
head = push(head, 13);
head = push(head, 11);
head = push(head, 11);
head = push(head, 11);
System.out.printf("\n Linked list before duplicate removal ");
printList(head);
/* Remove duplicates from linked list */
Node h = removeDuplicates(head);
System.out.printf("\n Linked list after duplicate removal ");
printList(h);
}
}
// This code is contributed by Arnab Kundu
Python
# Python Program to remove duplicates
# from a sorted linked list
# A linked list node
class Node:
def __init__(self, new_data):
self.data = new_data
self.next = None
# The function removes duplicates from a sorted list
def removeDuplicates( head) :
# if head is None then return
if (head == None) :
return None
# Remove duplicates from list after head
head.next = removeDuplicates(head.next)
# Check if head itself is duplicate
if (head.next != None and
head.next.data == head.data):
res = head.next
return res
return head
# UTILITY FUNCTIONS
# Function to insert a node at
#the beginning of the linked list
def push( head_ref, new_data) :
new_node = Node(0)
new_node.data = new_data
new_node.next = (head_ref)
(head_ref) = new_node
return head_ref
# Function to print nodes in a given linked list
def printList(node) :
while (node != None) :
print(node.data,end=" ")
node = node.next
# Driver program to test above functions
# Start with the empty list
head = None
# Let us create a sorted linked list to test the functions
# Created linked list will be 11.11.11.13.13.20
head = push(head, 20)
head = push(head, 13)
head = push(head, 13)
head = push(head, 11)
head = push(head, 11)
head = push(head, 11)
print("\n Linked list before duplicate removal ")
printList(head)
# Remove duplicates from linked list
h = removeDuplicates(head)
print("\n Linked list after duplicate removal ")
printList(h)
# This code is contributed by Arnab Kundu
C#
/* C# Program to remove duplicates
from a sorted linked list */
using System;
class GFG
{
/* Link list node */
public class Node
{
public int data;
public Node next;
};
/* The function removes duplicates from a sorted list */
static Node removeDuplicates( Node head)
{
/* if head is null then return*/
if (head == null)
return null;
/* Remove duplicates from list after head */
head.next = removeDuplicates(head.next);
// Check if head itself is duplicate
if (head.next != null &&
head.next.data == head.data)
{
Node res = head.next;
return res;
}
return head;
}
/* UTILITY FUNCTIONS */
/* Function to insert a node at
the beginning of the linked list */
static Node 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;
return head_ref;
}
/* Function to print nodes in a given linked list */
static void printList( Node node)
{
while (node != null)
{
Console.Write("{0} ", node.data);
node = node.next;
}
}
/* Driver program to test above functions*/
public static void Main(String []args)
{
/* Start with the empty list */
Node head = null;
/* Let us create a sorted linked list to test the functions
Created linked list will be 11.11.11.13.13.20 */
head = push(head, 20);
head = push(head, 13);
head = push(head, 13);
head = push(head, 11);
head = push(head, 11);
head = push(head, 11);
Console.Write("\n Linked list before duplicate removal ");
printList(head);
/* Remove duplicates from linked list */
Node h = removeDuplicates(head);
Console.Write("\n Linked list after duplicate removal ");
printList(h);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
/* JavaScript Program to remove duplicates
from a sorted linked list */
/* Link list node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
/* The function removes duplicates from a sorted list */
function removeDuplicates(head) {
/* if head is null then return*/
if (head == null) return null;
/* Remove duplicates from list after head */
head.next = removeDuplicates(head.next);
// Check if head itself is duplicate
if (head.next != null && head.next.data == head.data) {
var res = head.next;
return res;
}
return head;
}
/* UTILITY FUNCTIONS */
/* 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;
return head_ref;
}
/* Function to print nodes in a given linked list */
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
/* Driver program to test above functions*/
/* Start with the empty list */
var head = null;
/* Let us create a sorted linked list to test the functions
Created linked list will be 11.11.11.13.13.20 */
head = push(head, 20);
head = push(head, 13);
head = push(head, 13);
head = push(head, 11);
head = push(head, 11);
head = push(head, 11);
document.write("Linked list before duplicate removal ");
printList(head);
/* Remove duplicates from linked list */
var h = removeDuplicates(head);
document.write("<br> Linked list after duplicate removal ");
printList(h);
</script>
Producción:
Linked list before duplicate removal 11 11 11 13 13 20 Linked list after duplicate removal 11 13 20