Eliminar todas las ocurrencias de duplicados de una Lista Vinculada ordenada

Dada una lista enlazada ordenada, elimine todos los Nodes que tengan números duplicados (todas las ocurrencias), dejando solo los números que aparecen una vez en la lista original. 
Ejemplos:

Input : 23->28->28->35->49->49->53->53
Output : 23->35

Input : 11->11->11->11->75->75
Output : empty List

Tenga en cuenta que esto es diferente de Eliminar duplicados de la lista vinculada

La idea es mantener un puntero (prev) al Node que está justo antes del bloque de Nodes que estamos buscando duplicados. En el primer ejemplo, el puntero anterior apuntaría a 23 mientras buscamos duplicados para el Node 28. Una vez que lleguemos al último Node duplicado con valor 28 ( nómbrelo puntero actual ), podemos hacer que el siguiente campo del Node anterior sea el next of current y actualice current=current.next . Esto eliminaría el bloque de Nodes con valor 28 que tiene duplicados.

Implementación:

C++

// C++ program to remove all
// occurrences of duplicates
// from a sorted 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 print nodes
// in a given linked list.
void printList(struct Node* node)
{
    while (node != NULL) {
        cout<<node->data<<" ";
        node = node->next;
    }
}
  
// Function to remove all occurrences
// of duplicate elements
void removeAllDuplicates(struct Node*& start)
{
    // create a dummy node
    // that acts like a fake
    // head of list pointing
    // to the original head
    Node* dummy = new Node;
  
    // dummy node points
    // to the original head
    dummy->next = start;
  
    // Node pointing to last
    // node which has no duplicate.
    Node* prev = dummy;
  
    // Node used to traverse
    // the linked list.
    Node* current = start;
  
    while (current != NULL) {
        // Until the current and
        // previous values are
        // same, keep updating current
        while (current->next != NULL && prev->next->data == current->next->data)
            current = current->next;
  
        // if current has unique value
        // i.e current is not updated,
        // Move the prev pointer to
        // next node
        if (prev->next == current)
            prev = prev->next;
  
        // when current is updated
        // to the last duplicate
        // value of that segment,
        // make prev the next of current
        else
            prev->next = current->next;
  
        current = current->next;
    }
  
    // update original head to
    // the next of dummy node
    start = dummy->next;
}
  
// Driver Code
int main()
{
    // 23->28->28->35->49->49->53->53
    struct Node* start = newNode(23);
    start->next = newNode(28);
    start->next->next = newNode(28);
    start->next->next->next = newNode(35);
    start->next->next->next->next = newNode(49);
    start->next->next->next->next->next = newNode(49);
    start->next->next->next->next->next->next = newNode(53);
    start->next->next->next->next->next->next->next = newNode(53);
    cout << "List before removal of duplicates\n";
    printList(start);
  
    removeAllDuplicates(start);
  
    cout << "\nList after removal of duplicates\n";
    printList(start);
    return 0;
}
  
// This code is contributed by Aditya Kumar (adityakumar129)

C

// C++ program to remove all
// occurrences of duplicates
// from a sorted linked list.
#include<stdio.h>
#include<stdlib.h>
  
// A linked list node
typedef struct Node {
    int data;
    struct Node* next;
}Node;
  
// Utility function
// to create a new Node
struct Node* newNode(int data)
{
    Node* temp = (Node *)malloc(sizeof(Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}
  
// Function to print nodes
// in a given linked list.
void printList(Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}
  
// Function to remove all occurrences
// of duplicate elements
void removeAllDuplicates(Node* start)
{
    // create a dummy node
    // that acts like a fake
    // head of list pointing
    // to the original head
    Node* dummy = (Node *)malloc(sizeof(Node));
  
    // dummy node points
    // to the original head
    dummy->next = start;
  
    // Node pointing to last
    // node which has no duplicate.
    Node* prev = dummy;
  
    // Node used to traverse
    // the linked list.
    Node* current = start;
  
    while (current != NULL) {
        // Until the current and
        // previous values are
        // same, keep updating current
        while (current->next != NULL && prev->next->data == current->next->data)
            current = current->next;
  
        // if current has unique value
        // i.e current is not updated,
        // Move the prev pointer to
        // next node
        if (prev->next == current)
            prev = prev->next;
  
        // when current is updated
        // to the last duplicate
        // value of that segment,
        // make prev the next of current
        else
            prev->next = current->next;
  
        current = current->next;
    }
  
    // update original head to
    // the next of dummy node
    start = dummy->next;
}
  
// Driver Code
int main()
{
    // 23->28->28->35->49->49->53->53
    struct Node* start = newNode(23);
    start->next = newNode(28);
    start->next->next = newNode(28);
    start->next->next->next = newNode(35);
    start->next->next->next->next = newNode(49);
    start->next->next->next->next->next = newNode(49);
    start->next->next->next->next->next->next = newNode(53);
    start->next->next->next->next->next->next->next = newNode(53);
    printf("List before removal of duplicates\n");
    printList(start);
  
    removeAllDuplicates(start);
  
    printf("\nList after removal of duplicates\n");
    printList(start);
    return 0;
}
  
// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program to remove all occurrences of
// duplicates from a sorted linked list 
  
// class to create Linked lIst 
class LinkedList{
      
// head of linked list 
Node head = null; 
class Node
{
      
    // value in the node 
    int val; 
    Node next;
    Node(int v)
    {
          
        // default value of the next
        // pointer field 
        val = v;
        next = null;
    }
}
  
// Function to insert data nodes into
// the Linked List at the front
public void insert(int data)
{
    Node new_node = new Node(data);
    new_node.next = head;
    head = new_node;
}
  
// Function to remove all occurrences
// of duplicate elements 
public void removeAllDuplicates()
{
      
    // Create a dummy node that acts like a fake
    // head of list pointing to the original head
    Node dummy = new Node(0);
  
    // Dummy node points to the original head
    dummy.next = head;
    Node prev = dummy;
    Node current = head;
  
    while (current != null)
    {
        // Until the current and previous values
        // are same, keep updating current 
        while (current.next != null &&
               prev.next.val == current.next.val)
               current = current.next;
  
        // If current has unique value i.e current
        // is not updated, Move the prev pointer
        // to next node
        if (prev.next == current)
            prev = prev.next;
  
        // When current is updated to the last
        // duplicate value of that segment, make
        // prev the next of current*/
        else
            prev.next = current.next;
  
        current = current.next;
    }
  
    // Update original head to the next of dummy
    // node 
    head = dummy.next;
}
  
// Function to print the list elements
public void printList()
{
    Node trav = head;
    if (head == null)
        System.out.print(" List is empty" );
          
    while (trav != null)
    {
        System.out.print(trav.val + " ");
        trav = trav.next;
    }
}
  
// Driver code
public static void main(String[] args)
{
    LinkedList ll = new LinkedList();
    ll.insert(53);
    ll.insert(53);
    ll.insert(49);
    ll.insert(49);
    ll.insert(35);
    ll.insert(28);
    ll.insert(28);
    ll.insert(23);
      
    System.out.println("Before removal of duplicates");
    ll.printList();
  
    ll.removeAllDuplicates();
  
    System.out.println("\nAfter removal of duplicates");
    ll.printList();
}
}

Python3

# Python3 implementation for the above approach
  
# Creating node
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
          
    # add node into beganing of linked list
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node
        return new_node
          
    # Function to remove all occurrences
    # of duplicate elements
    def removeAllDuplicates(self, temp):
          
        # temp is head node of linkedlist
        curr = temp
        # print(' print something')
        head = prev = Node(None)
        head.next = curr
  
        # Here we use same as we do in removing 
        # duplicates and only extra thing is that
        # we need to remove all elements 
        # having duplicates that we did in 30-31
        while curr and curr.next:
              
            # until the current value and next 
            # value are same keep updating the current value
            if curr.val == curr.next.val:
                while(curr and curr.next and 
                      curr.val == curr.next.val):
                    curr = curr.next
                      
                    # still one of duplicate values left
                    # so point prec to curr
                curr = curr.next
                prev.next = curr
            else:
                prev = prev.next
                curr = curr.next
        return head.next
          
    # for print the linkedlist
    def printList(self):
        temp1 = self.head
        while temp1 is not None:
            print(temp1.val, end = " ")
            temp1 = temp1.next
              
    # For getting head of linkedlist
    def get_head(self):
        return self.head
  
# Driver Code
if __name__=='__main__':
    llist = LinkedList()
    llist.push(53)
    llist.push(53)
    llist.push(49)
    llist.push(49)
    llist.push(35)
    llist.push(28)
    llist.push(28)
    llist.push(23)
      
    print('Created linked list is:')
    llist.printList()
    print('\nLinked list after deletion of duplicates:')
    head1 = llist.get_head()
    #print(head1)
    llist.removeAllDuplicates(head1)
    llist.printList()
          
# This code is contributed 
# by PRAVEEN KUMAR(IIIT KALYANI)

C#

/* C# program to remove all occurrences of
duplicates from a sorted linked list */
  
using System;
  
/* class to create Linked lIst */
public class LinkedList
{
    Node head = null; /* head of linked list */
    class Node
    {
        public int val; /* value in the node */
        public Node next;
        public Node(int v)
        {
            /* default value of the next
            pointer field */
            val = v;
            next = null;
        }
    }
  
    /* Function to insert data nodes into
    the Linked List at the front */
    public void insert(int data)
    {
        Node new_node = new Node(data);
        new_node.next = head;
        head = new_node;
    }
  
    /* Function to remove all occurrences
    of duplicate elements */
    public void removeAllDuplicates()
    {
    /* create a dummy node that acts like a fake
        head of list pointing to the original head*/
        Node dummy = new Node(0);
  
        /* dummy node points to the original head*/
        dummy.next = head;
        Node prev = dummy;
        Node current = head;
  
        while (current != null)
        {
            /* Until the current and previous values
            are same, keep updating current */
            while (current.next != null &&
                prev.next.val == current.next.val)
                current = current.next;
  
            /* if current has unique value i.e current
                is not updated, Move the prev pointer
                to next node*/
            if (prev.next == current)
                prev = prev.next;
  
            /* when current is updated to the last
            duplicate value of that segment, make
            prev the next of current*/
            else
                prev.next = current.next;
  
            current = current.next;
        }
  
        /* update original head to the next of dummy
        node */
        head = dummy.next;
    }
  
    /* Function to print the list elements */
    public void printList()
    {
        Node trav = head;
        if (head == null)
            Console.Write(" List is empty" );
        while (trav != null)
        {
            Console.Write(trav.val + " ");
            trav = trav.next;
        }
    }
  
    /* Driver code */
    public static void Main(String[] args)
    {
        LinkedList ll = new LinkedList();
        ll.insert(53);
        ll.insert(53);
        ll.insert(49);
        ll.insert(49);
        ll.insert(35);
        ll.insert(28);
        ll.insert(28);
        ll.insert(23);
        Console.WriteLine("Before removal of duplicates");
        ll.printList();
  
        ll.removeAllDuplicates();
  
        Console.WriteLine("\nAfter removal of duplicates");
        ll.printList();
    }
}
  
// This code is contributed by Rajput-Ji

Javascript

// Remove all occurrences of duplicates from a sorted Linked List
  
class Node {
    constructor(val, next = null) {
        this.data = val;
        this.next = next;
    } 
}
  
const node1 = new Node(11);
const node2 = new Node(11);
const node3 = new Node(11);
const node4 = new Node(75);
const node5 = new Node(75);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
  
const removeDuplicate = (head) => {
    let current = head;
    let prev = null;
    while(current) {
        if (current.next && current.data == current.next.data) {
           let pivot = current;
           let newCurrent = current.next
           while (newCurrent && pivot.data === newCurrent.data) {
               // removing current;
               pivot.next = newCurrent.next;
               // increment
               newCurrent = newCurrent.next;
           }
           // removing first duplicate element
           if (prev) prev.next = pivot.next;
           else head = pivot.next
             
           current = pivot.next
        } else {
            prev = current;
            current = current.next;
        }
    }
    return head;
}
  
console.log(JSON.stringify(removeDuplicate(node1)));
Producción

List before removal of duplicates
23 28 28 35 49 49 53 53 
List after removal of duplicates
23 35 

Complete Interview Preparation - GFG

Complejidad de tiempo: O(n)
Espacio auxiliar: O(1) porque no se requiere espacio adicional en la eliminación de duplicados

Este artículo es una contribución de Saloni Baweja . 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *