Dada una Lista enlazada individual sin clasificar que consta de N Nodes que pueden contener elementos duplicados, la tarea es eliminar todos los elementos duplicados excepto la última aparición de la Lista enlazada .
Ejemplos:
Entrada: 1 -> 2 -> 7 -> 3 -> 2 -> 5 -> 1
Salida: 7 -> 3 -> 2 -> 5 -> 1
Explicación:
Lista enlazada dada: 1 -> 2 -> 7 – > 3 -> 2 -> 5 -> 1
Elementos duplicados: 1, 2
Lista enlazada modificada: 7 -> 3 -> 2 -> 5 -> 1Entrada: 1 -> 2 -> 3 -> 4 -> 5
Salida: 1 -> 2 -> 3 -> 4 -> 5
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice un Node ficticio y haga que sea el siguiente punto a la cabeza .
- Invierta la lista enlazada dada.
- Inicialice un conjunto desordenado , digamos visitado, para almacenar los Nodes ya visitados.
- Inicialice dos Nodes, digamos currnode, apuntando al Node ficticio , y nextnode, para almacenar el siguiente Node del Node actual .
- Iterar sobre la lista enlazada y comprobar si los datos del siguiente Node del Node actual ya han sido visitados o no.
- Si ya está visitado, realice los siguientes pasos:
- Inicialice un nuevo Node, digamos duplicado , para almacenar el siguiente Node, que en este caso es un Node duplicado.
- Haga que el siguiente punto actual sea el siguiente del siguiente Node .
- De lo contrario:
- Inserte los datos de nextnode en el conjunto visitado .
- Hacer nextnode como currentnode .
- Finalmente, invierta la lista enlazada modificada y regrese.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Node class
class Node {
public:
int data;
Node* next;
Node(int x)
{
this->data = x;
this->next = NULL;
}
};
// Function to reverse a Linked List
Node* reverseList(Node* head)
{
Node *prev = NULL, *nextNode = NULL;
while (head != NULL) {
// Point to next node
// of the current node
nextNode = head->next;
// Point next of current
// to the previous node
head->next = prev;
prev = head;
head = nextNode;
}
return prev;
}
// Function to modify a linked list
// such that it contains only the
// last occurrence of duplicate elements
Node* Remove_Dup_Keep_Last_Occurence(
Node* head)
{
// Make a dummy node
Node* dummy = new Node(-1);
dummy->next = head;
// Reverse the given Linked List
dummy->next = reverseList(dummy->next);
// Stores duplicate elements
unordered_set<int> visited;
Node *currNode = dummy, *nextNode;
// Iterate over the list
while (currNode != NULL
&& currNode->next != NULL) {
nextNode = currNode->next;
// Check if data of the next node of the
// current node is already visited or not
if (visited.count(nextNode->data) != 0) {
// Stores the duplicate pointer
Node* duplicate = nextNode;
currNode->next = nextNode->next;
// Erase memory of duplicate pointer
delete duplicate;
}
else {
// Mark as visited to data of nextNode
visited.insert(nextNode->data);
// Go for the next node
currNode = nextNode;
}
}
// Reverse the modified linked list
dummy->next = reverseList(dummy->next);
return dummy->next;
}
// Function to print a Linked List
void print_Linked_List(Node* head)
{
Node* curr = head;
while (curr != NULL) {
cout << curr->data << ' ';
curr = curr->next;
}
}
// Driver Code
int main()
{
// Given Input
Node* head = new Node(3);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(1);
head->next->next->next->next = new Node(5);
head->next->next->next->next->next = new Node(1);
head->next->next->next->next->next->next = new Node(6);
head = Remove_Dup_Keep_Last_Occurence(head);
// Function Call
print_Linked_List(head);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Node class
static class Node {
int data;
Node next;
Node(int x)
{
this.data = x;
this.next = null;
}
};
// Function to reverse a Linked List
static Node reverseList(Node head)
{
Node prev = null, nextNode = null;
while (head != null) {
// Point to next node
// of the current node
nextNode = head.next;
// Point next of current
// to the previous node
head.next = prev;
prev = head;
head = nextNode;
}
return prev;
}
// Function to modify a linked list
// such that it contains only the
// last occurrence of duplicate elements
static Node Remove_Dup_Keep_Last_Occurence(
Node head)
{
// Make a dummy node
Node dummy = new Node(-1);
dummy.next = head;
// Reverse the given Linked List
dummy.next = reverseList(dummy.next);
// Stores duplicate elements
HashSet<Integer> visited = new HashSet<Integer>();
Node currNode = dummy;
Node nextNode;
// Iterate over the list
while (currNode != null
&& currNode.next != null) {
nextNode = currNode.next;
// Check if data of the next node of the
// current node is already visited or not
if (visited.contains(nextNode.data)) {
// Stores the duplicate pointer
Node duplicate = nextNode;
currNode.next = nextNode.next;
// Erase memory of duplicate pointer
duplicate=null;
}
else {
// Mark as visited to data of nextNode
visited.add(nextNode.data);
// Go for the next node
currNode = nextNode;
}
}
// Reverse the modified linked list
dummy.next = reverseList(dummy.next);
return dummy.next;
}
// Function to print a Linked List
static void print_Linked_List(Node head)
{
Node curr = head;
while (curr != null) {
System.out.print(curr.data +" ");
curr = curr.next;
}
}
// Driver Code
public static void main(String[] args)
{
// Given Input
Node head = new Node(3);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(5);
head.next.next.next.next.next = new Node(1);
head.next.next.next.next.next.next = new Node(6);
head = Remove_Dup_Keep_Last_Occurence(head);
// Function Call
print_Linked_List(head);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program for the above approach # Node class class Node: def __init__(self, data): self.data = data; self.next = None; # Function to reverse a Linked List def reverseList(head): prev = None; nextNode = None; while (head != None): # Point to next Node # of the current Node nextNode = head.next; # Point next of current # to the previous Node head.next = prev; prev = head; head = nextNode; return prev; # Function to modify a linked list # such that it contains only the # last occurrence of duplicate elements def Remove_Dup_Keep_Last_Occurence(head): # Make a dummy Node dummy = Node(-1); dummy.next = head; # Reverse the given Linked List dummy.next = reverseList(dummy.next); # Stores duplicate elements visited =set(); currNode = dummy; nextNode = None; # Iterate over the list while (currNode != None and currNode.next != None): nextNode = currNode.next; # Check if data of the next Node of the # current Node is already visited or not if (visited.__contains__(nextNode.data)): # Stores the duplicate pointer duplicate = nextNode; currNode.next = nextNode.next; # Erase memory of duplicate pointer duplicate = None; else: # Mark as visited to data of nextNode visited.add(nextNode.data); # Go for the next Node currNode = nextNode; # Reverse the modified linked list dummy.next = reverseList(dummy.next); return dummy.next; # Function to pra Linked List def print_Linked_List(head): curr = head; while (curr != None): print(curr.data, end=" "); curr = curr.next; # Driver Code if __name__ == '__main__': # Given Input head = Node(3); head.next = Node(2); head.next.next = Node(3); head.next.next.next = Node(1); head.next.next.next.next = Node(5); head.next.next.next.next.next = Node(1); head.next.next.next.next.next.next = Node(6); head = Remove_Dup_Keep_Last_Occurence(head); # Function Call print_Linked_List(head); # This code is contributed by shikhasingrajput
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Node class
public class Node {
public int data;
public Node next;
public Node(int x) {
this.data = x;
this.next = null;
}
};
// Function to reverse a Linked List
static Node reverseList(Node head) {
Node prev = null, nextNode = null;
while (head != null) {
// Point to next node
// of the current node
nextNode = head.next;
// Point next of current
// to the previous node
head.next = prev;
prev = head;
head = nextNode;
}
return prev;
}
// Function to modify a linked list
// such that it contains only the
// last occurrence of duplicate elements
static Node Remove_Dup_Keep_Last_Occurence(Node head)
{
// Make a dummy node
Node dummy = new Node(-1);
dummy.next = head;
// Reverse the given Linked List
dummy.next = reverseList(dummy.next);
// Stores duplicate elements
HashSet<int> visited = new HashSet<int>();
Node currNode = dummy;
Node nextNode;
// Iterate over the list
while (currNode != null && currNode.next != null) {
nextNode = currNode.next;
// Check if data of the next node of the
// current node is already visited or not
if (visited.Contains(nextNode.data)) {
// Stores the duplicate pointer
Node duplicate = nextNode;
currNode.next = nextNode.next;
// Erase memory of duplicate pointer
duplicate = null;
} else {
// Mark as visited to data of nextNode
visited.Add(nextNode.data);
// Go for the next node
currNode = nextNode;
}
}
// Reverse the modified linked list
dummy.next = reverseList(dummy.next);
return dummy.next;
}
// Function to print a Linked List
static void print_Linked_List(Node head) {
Node curr = head;
while (curr != null) {
Console.Write(curr.data + " ");
curr = curr.next;
}
}
// Driver Code
public static void Main(String[] args) {
// Given Input
Node head = new Node(3);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(5);
head.next.next.next.next.next = new Node(1);
head.next.next.next.next.next.next = new Node(6);
head = Remove_Dup_Keep_Last_Occurence(head);
// Function Call
print_Linked_List(head);
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// javascript program for the above approach
// Node class
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Function to reverse a Linked List
function reverseList(head) {
var prev = null, nextNode = null;
while (head != null) {
// Point to next node
// of the current node
nextNode = head.next;
// Point next of current
// to the previous node
head.next = prev;
prev = head;
head = nextNode;
}
return prev;
}
// Function to modify a linked list
// such that it contains only the
// last occurrence of duplicate elements
function Remove_Dup_Keep_Last_Occurence(head)
{
// Make a dummy node
var dummy = new Node(-1);
dummy.next = head;
// Reverse the given Linked List
dummy.next = reverseList(dummy.next);
// Stores duplicate elements
var visited = new Set();
var currNode = dummy;
var nextNode;
// Iterate over the list
while (currNode != null && currNode.next != null) {
nextNode = currNode.next;
// Check if data of the next node of the
// current node is already visited or not
if (visited.has(nextNode.data)) {
// Stores the duplicate pointer
var duplicate = nextNode;
currNode.next = nextNode.next;
// Erase memory of duplicate pointer
duplicate = null;
} else {
// Mark as visited to data of nextNode
visited.add(nextNode.data);
// Go for the next node
currNode = nextNode;
}
}
// Reverse the modified linked list
dummy.next = reverseList(dummy.next);
return dummy.next;
}
// Function to print a Linked List
function print_Linked_List(head) {
var curr = head;
while (curr != null) {
document.write(curr.data + " ");
curr = curr.next;
}
}
// Driver Code
// Given Input
var head = new Node(3);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(5);
head.next.next.next.next.next = new Node(1);
head.next.next.next.next.next.next = new Node(6);
head = Remove_Dup_Keep_Last_Occurence(head);
// Function Call
print_Linked_List(head);
// This code contributed by umadevi9616
</script>
Producción:
2 3 5 1 6
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por srivastavaharshit848 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA