Dada una lista ordenada doblemente enlazada que contiene n Nodes. El problema es eliminar los Nodes duplicados de la lista dada.
Ejemplos:
Algoritmo:
removeDuplicates(head_ref, x)
if head_ref == NULL
return
Initialize current = head_ref
while current->next != NULL
if current->data == current->next->data
deleteNode(head_ref, current->next)
else
current = current->next
El algoritmo para deleteNode(head_ref, current) (que elimina el Node usando el puntero al Node) se analiza en esta publicación.
Implementación:
C++
/* C++ implementation to remove duplicates from a
sorted doubly linked list */
#include <bits/stdc++.h>
using namespace std;
/* a node of the doubly linked list */
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
/* Function to delete a node in a Doubly Linked List.
head_ref --> pointer to head node pointer.
del --> pointer to node to be deleted. */
void deleteNode(struct Node** head_ref, struct Node* del)
{
/* base case */
if (*head_ref == NULL || del == NULL)
return;
/* If node to be deleted is head node */
if (*head_ref == del)
*head_ref = del->next;
/* Change next only if node to be deleted
is NOT the last node */
if (del->next != NULL)
del->next->prev = del->prev;
/* Change prev only if node to be deleted
is NOT the first node */
if (del->prev != NULL)
del->prev->next = del->next;
/* Finally, free the memory occupied by del*/
free(del);
}
/* function to remove duplicates from a
sorted doubly linked list */
void removeDuplicates(struct Node** head_ref)
{
/* if list is empty */
if ((*head_ref) == NULL)
return;
struct Node* current = *head_ref;
struct Node* next;
/* traverse the list till the last node */
while (current->next != NULL) {
/* Compare current node with next node */
if (current->data == current->next->data)
/* delete the node pointed to by
'current->next' */
deleteNode(head_ref, current->next);
/* else simply move to the next node */
else
current = current->next;
}
}
/* Function to insert a node at the beginning
of the Doubly Linked List */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*)malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* since we are adding at the beginning,
prev is always NULL */
new_node->prev = NULL;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* change prev of head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given doubly linked list */
void printList(struct Node* head)
{
/* if list is empty */
if (head == NULL)
cout << "Doubly Linked list empty";
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Create the doubly linked list:
4<->4<->4<->4<->6<->8<->8<->10<->12<->12 */
push(&head, 12);
push(&head, 12);
push(&head, 10);
push(&head, 8);
push(&head, 8);
push(&head, 6);
push(&head, 4);
push(&head, 4);
push(&head, 4);
push(&head, 4);
cout << "Original Doubly linked list:n";
printList(head);
/* remove duplicate nodes */
removeDuplicates(&head);
cout << "\nDoubly linked list after"
" removing duplicates:n";
printList(head);
return 0;
}
Java
/* Java implementation to remove duplicates from a
sorted doubly linked list */
public class removeDuplicatesFromSortedList {
/* function to remove duplicates from a
sorted doubly linked list */
public static void removeDuplicates(Node head)
{
/* if list is empty */
if (head== null)
return;
Node current = head;
/* traverse the list till the last node */
while (current.next != null)
{
/* Compare current node with next node */
if (current.data == current.next.data)
/* delete the node pointed to by
' current->next' */
deleteNode(head, current.next);
/* else simply move to the next node */
else
current = current.next;
}
}
/* Function to delete a node in a Doubly Linked List.
head_ref --> pointer to head node pointer.
del --> pointer to node to be deleted. */
public static void deleteNode(Node head, Node del)
{
/* base case */
if(head==null || del==null)
{
return ;
}
/* If node to be deleted is head node */
if(head==del)
{
head=del.next;
}
/* Change next only if node to be deleted
is NOT the last node */
if(del.next!=null)
{
del.next.prev=del.prev;
}
/* Change prev only if node to be deleted
is NOT the first node */
if (del.prev != null)
del.prev.next = del.next;
}
/* Function to insert a node at the beginning
of the Doubly Linked List */
public static Node push(Node head, int data)
{
/* allocate node */
Node newNode=new Node(data);
/* since we are adding at the beginning,
prev is always NULL */
newNode.prev=null;
/* link the old list off the new node */
newNode.next =head;
/* change prev of head node to new node */
if(head!=null)
{
head.prev=newNode;
}
head=newNode;
return head;
}
/* Function to print nodes in a given doubly linked list */
public static void printList(Node head)
{
if (head == null)
System.out.println("Doubly Linked list empty");
while (head != null)
{
System.out.print(head.data+" ") ;
head = head.next;
}
}
public static void main(String args[]) {
Node head=null;
head=push(head, 12);
head=push(head, 12);
head=push(head, 10);
head=push(head, 8);
head=push(head, 8);
head=push(head, 6);
head=push(head, 4);
head=push(head, 4);
head=push(head, 4);
head=push(head, 4);
System.out.println("Original Doubly LinkedList");
printList(head);
/* remove duplicate nodes */
removeDuplicates(head);
System.out.println("\nDoubly linked list after removing duplicates:");
printList(head);
}
}
class Node
{
int data;
Node next,prev;
Node(int data)
{
this.data=data;
next=null;
prev=null;
}
}
//This code is contributed by Gaurav Tiwari
Python
# Python implementation to remove duplicates from a
# sorted doubly linked list
# A linked list node
class Node:
def __init__(self, new_data):
self.data = new_data
self.next = None
self.prev = None
# Function to _delete a node in a Doubly Linked List.
# head_ref -. pointer to head node pointer.
# _del -. pointer to node to be _deleted.
def _deleteNode(head_ref, _del):
# base case
if (head_ref == None or _del == None):
return
# If node to be _deleted is head node
if (head_ref == _del):
head_ref = _del.next
# Change next only if node to be _deleted
# is NOT the last node
if (_del.next != None):
_del.next.prev = _del.prev
# Change prev only if node to be _deleted
# is NOT the first node
if (_del.prev != None):
_del.prev.next = _del.next
return head_ref
# function to remove duplicates from a
# sorted doubly linked list
def removeDuplicates(head_ref):
# if list is empty
if ((head_ref) == None):
return None
current = head_ref
next = None
# traverse the list till the last node
while (current.next != None) :
# Compare current node with next node
if (current.data == current.next.data):
# _delete the node pointed to by
# 'current.next'
_deleteNode(head_ref, current.next)
# else simply move to the next node
else:
current = current.next
return head_ref
# Function to insert a node at the beginning
# of the Doubly Linked List
def push(head_ref, new_data):
# allocate node
new_node = Node(0)
# put in the data
new_node.data = new_data
# since we are adding at the beginning,
# prev is always None
new_node.prev = None
# link the old list off the new node
new_node.next = (head_ref)
# change prev of head node to new node
if ((head_ref) != None):
(head_ref).prev = new_node
# move the head to point to the new node
(head_ref) = new_node
return head_ref
# Function to print nodes in a given doubly linked list
def printList(head):
# if list is empty
if (head == None):
print("Doubly Linked list empty")
while (head != None) :
print(head.data, end = " ")
head = head.next
# Driver program to test above functions
# Start with the empty list
head = None
# Create the doubly linked list:
# 4<->4<->4<->4<->6<->8<->8<->10<->12<->12
head = push(head, 12)
head = push(head, 12)
head = push(head, 10)
head = push(head, 8)
head = push(head, 8)
head = push(head, 6)
head = push(head, 4)
head = push(head, 4)
head = push(head, 4)
head = push(head, 4)
print( "Original Doubly linked list:\n")
printList(head)
# remove duplicate nodes
head = removeDuplicates(head)
print("\nDoubly linked list after removing duplicates:")
printList(head)
# This code is contributed by Arnab Kundu
C#
/* C# implementation to remove duplicates from a
sorted doubly linked list */
using System;
public class removeDuplicatesFromSortedList
{
/* function to remove duplicates from a
sorted doubly linked list */
public static void removeDuplicates(Node head)
{
/* if list is empty */
if (head == null)
return;
Node current = head;
/* traverse the list till the last node */
while (current.next != null)
{
/* Compare current node with next node */
if (current.data == current.next.data)
/* delete the node pointed to by
'current->next' */
deleteNode(head, current.next);
/* else simply move to the next node */
else
current = current.next;
}
}
/* Function to delete a node in a Doubly Linked List.
head_ref --> pointer to head node pointer.
del --> pointer to node to be deleted. */
public static void deleteNode(Node head, Node del)
{
/* base case */
if(head == null || del == null)
{
return ;
}
/* If node to be deleted is head node */
if(head == del)
{
head = del.next;
}
/* Change next only if node to be deleted
is NOT the last node */
if(del.next != null)
{
del.next.prev = del.prev;
}
/* Change prev only if node to be deleted
is NOT the first node */
if (del.prev != null)
del.prev.next = del.next;
}
/* Function to insert a node at the beginning
of the Doubly Linked List */
public static Node push(Node head, int data)
{
/* allocate node */
Node newNode = new Node(data);
/* since we are adding at the beginning,
prev is always NULL */
newNode.prev = null;
/* link the old list off the new node */
newNode.next = head;
/* change prev of head node to new node */
if(head != null)
{
head.prev = newNode;
}
head = newNode;
return head;
}
/* Function to print nodes in a given doubly linked list */
public static void printList(Node head)
{
if (head == null)
Console.WriteLine("Doubly Linked list empty");
while (head != null)
{
Console.Write(head.data + " ") ;
head = head.next;
}
}
// Driver code
public static void Main(String []args)
{
Node head = null;
head = push(head, 12);
head = push(head, 12);
head = push(head, 10);
head = push(head, 8);
head = push(head, 8);
head = push(head, 6);
head = push(head, 4);
head = push(head, 4);
head = push(head, 4);
head = push(head, 4);
Console.WriteLine("Original Doubly LinkedList");
printList(head);
/* remove duplicate nodes */
removeDuplicates(head);
Console.WriteLine("\nDoubly linked list after" +
"removing duplicates:");
printList(head);
}
}
public class Node
{
public int data;
public Node next,prev;
public Node(int data)
{
this.data = data;
next = null;
prev = null;
}
}
// This code is contributed by 29AjayKumar.
Javascript
<script>
/* javascript implementation to remove duplicates from a
sorted doubly linked list */
class Node {
constructor(val){
this.data = val;
this.prev = null;
this.next = null;
}
}
/*
* function to remove duplicates from a sorted doubly linked list
*/
function removeDuplicates(head) {
/* if list is empty */
if (head == null)
return;
var current = head;
/* traverse the list till the last node */
while (current.next != null) {
/* Compare current node with next node */
if (current.data == current.next.data)
/*
* delete the node pointed to by ' current->next'
*/
deleteNode(head, current.next);
/* else simply move to the next node */
else
current = current.next;
}
}
/*
* Function to delete a node in a Doubly Linked List. head_ref --> pointer to
* head node pointer. del --> pointer to node to be deleted.
*/
function deleteNode(head, del) {
/* base case */
if (head == null || del == null) {
return;
}
/* If node to be deleted is head node */
if (head == del) {
head = del.next;
}
/*
* Change next only if node to be deleted is NOT the last node
*/
if (del.next != null) {
del.next.prev = del.prev;
}
/*
* Change prev only if node to be deleted is NOT the first node
*/
if (del.prev != null)
del.prev.next = del.next;
}
/*
* Function to insert a node at the beginning of the Doubly Linked List
*/
function push(head , data) {
/* allocate node */
var newNode = new Node(data);
/*
* since we are adding at the beginning, prev is always NULL
*/
newNode.prev = null;
/* link the old list off the new node */
newNode.next = head;
/* change prev of head node to new node */
if (head != null) {
head.prev = newNode;
}
head = newNode;
return head;
}
/* Function to print nodes in a given doubly linked list */
function printList(head) {
if (head == null)
document.write("Doubly Linked list empty");
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
}
var head = null;
head = push(head, 12);
head = push(head, 12);
head = push(head, 10);
head = push(head, 8);
head = push(head, 8);
head = push(head, 6);
head = push(head, 4);
head = push(head, 4);
head = push(head, 4);
head = push(head, 4);
document.write("Original Doubly LinkedList<br/>");
printList(head);
/* remove duplicate nodes */
removeDuplicates(head);
document.write("<br/>Doubly linked list after removing duplicates:<br/>");
printList(head);
// This code contributed by gauravrajput1
</script>
Producción
Original Doubly linked list:n4 4 4 4 6 8 8 10 12 12 Doubly linked list after removing duplicates:n4 6 8 10 12
Complejidad de tiempo: O(n)
Complejidad de espacio: O(1) ya que se usa espacio constante para punteros
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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