Dada una lista enlazada que contiene algunos enteros aleatorios del 1 al n con muchos duplicados. Reemplace cada elemento duplicado que esté presente en la lista vinculada con los valores n+1, n+2, n+3 y así sucesivamente (comenzando de izquierda a derecha en la lista vinculada dada).
Ejemplos:
Input : 1 3 1 4 4 2 1
Output : 1 3 5 4 6 2 7
Replace 2nd occurrence of 1 with 5 i.e. (4+1)
2nd occurrence of 4 with 6 i.e. (4+2)
3rd occurrence of 1 with 7 i.e. (4+3)
Input : 1 1 1 4 3 2 2
Output : 1 5 6 4 3 2 7
Acercarse :
- Atraviese la lista enlazada, almacene las frecuencias de cada número presente en la lista enlazada en un mapa y, junto con él, encuentre el número entero máximo presente en la lista enlazada, es decir , maxNum .
- Ahora, recorra la lista enlazada nuevamente y si la frecuencia de cualquier número es mayor que 1, establezca su valor en -1 en el mapa en su primera aparición.
- La razón de esto es que en la próxima aparición de este número encontraremos su valor -1, lo que significa que este número ha ocurrido antes, cambie sus datos con maxNum + 1 e incremente maxNum.
A continuación se muestra la implementación de la idea.
C++
// C++ implementation of the approach
#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 replace duplicates from a
// linked list
void replaceDuplicates(struct Node* head)
{
// map to store the frequency of numbers
unordered_map<int, int> mymap;
Node* temp = head;
// variable to store the maximum number
// in linked list
int maxNum = 0;
// traverse the linked list to store
// the frequency of every number and
// find the maximum integer
while (temp) {
mymap[temp->data]++;
if (maxNum < temp->data)
maxNum = temp->data;
temp = temp->next;
}
// Traverse again the linked list
while (head) {
// Mark the node with frequency more
// than 1 so that we can change the
// 2nd occurrence of that number
if (mymap[head->data] > 1)
mymap[head->data] = -1;
// -1 means number has occurred
// before change its value
else if (mymap[head->data] == -1)
head->data = ++maxNum;
head = head->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;
}
cout << endl;
}
/* Driver program to test above function */
int main()
{
/* The constructed linked list is:
1->3->1->4->4->2->1*/
struct Node* head = newNode(1);
head->next = newNode(3);
head->next->next = newNode(1);
head->next->next->next = newNode(4);
head->next->next->next->next =
newNode(4);
head->next->next->next->next->
next = newNode(2);
head->next->next->next->next->
next->next = newNode(1);
cout << "Linked list before replacing"
<< " duplicates\n";
printList(head);
replaceDuplicates(head);
cout << "Linked list after replacing"
<< " duplicates\n";
printList(head);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Representation of node
static class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
};
// Function to insert a node at the beginning
static Node insert(Node head, int item)
{
Node temp = new Node(0);
temp.data = item;
temp.next = head;
head = temp;
return head;
}
// Function to replace duplicates from a
// linked list
static void replaceDuplicates( Node head)
{
// map to store the frequency of numbers
Map<Integer, Integer> mymap = new HashMap<>();
Node temp = head;
// variable to store the maximum number
// in linked list
int maxNum = 0;
// traverse the linked list to store
// the frequency of every number and
// find the maximum integer
while (temp != null)
{
mymap.put(temp.data,(mymap.get(temp.data) ==
null?0:mymap.get(temp.data))+1);
if (maxNum < temp.data)
maxNum = temp.data;
temp = temp.next;
}
// Traverse again the linked list
while (head != null)
{
// Mark the node with frequency more
// than 1 so that we can change the
// 2nd occurrence of that number
if (mymap.get(head.data) > 1)
mymap.put(head.data, -1);
// -1 means number has occurred
// before change its value
else if (mymap.get(head.data) == -1)
head.data = ++maxNum;
head = head.next;
}
}
// 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;
} System.out.println();
}
// Driver code
public static void main(String args[])
{
// The constructed linked list is:
// 1->3->1->4->4->2->1/
Node head = new Node(1);
head.next = new Node(3);
head.next.next = new Node(1);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(4);
head.next.next.next.next.
next = new Node(2);
head.next.next.next.next.
next.next = new Node(1);
System.out.println( "Linked list before replacing"
+ " duplicates\n");
printList(head);
replaceDuplicates(head);
System.out.println("Linked list after replacing"
+ " duplicates\n");
printList(head);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach
# A linked list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Utility function to create a new Node
def newNode(data):
temp = Node(data)
return temp
# Function to replace duplicates from a
# linked list
def replaceDuplicates(head):
# Map to store the frequency of numbers
mymap = dict()
temp = head
# Variable to store the maximum number
# in linked list
maxNum = 0
# Traverse the linked list to store
# the frequency of every number and
# find the maximum integer
while (temp):
if temp.data not in mymap:
mymap[temp.data] = 0
mymap[temp.data] += 1
if (maxNum < temp.data):
maxNum = temp.data
temp = temp.next
# Traverse again the linked list
while (head):
# Mark the node with frequency more
# than 1 so that we can change the
# 2nd occurrence of that number
if (mymap[head.data] > 1):
mymap[head.data] = -1
# -1 means number has occurred
# before change its value
elif (mymap[head.data] == -1):
maxNum += 1
head.data = maxNum
head = head.next
# Function to print nodes in a given
# linked list
def printList(node):
while (node != None):
print(node.data, end = ' ')
node = node.next
print()
# Driver code
if __name__=='__main__':
# The constructed linked list is:
# 1.3.1.4.4.2.1
head = newNode(1)
head.next = newNode(3)
head.next.next = newNode(1)
head.next.next.next = newNode(4)
head.next.next.next.next = newNode(4)
head.next.next.next.next.next = newNode(2)
head.next.next.next.next.next.next = newNode(1)
print("Linked list before replacing duplicates")
printList(head)
replaceDuplicates(head)
print("Linked list after replacing duplicates")
printList(head)
# This code is contributed by rutvik_56
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Representation of node
class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
};
// Function to insert a node at the beginning
static Node insert(Node head, int item)
{
Node temp = new Node(0);
temp.data = item;
temp.next = head;
head = temp;
return head;
}
// Function to replace duplicates from a
// linked list
static void replaceDuplicates( Node head)
{
// map to store the frequency of numbers
Dictionary<int,
int> mymap = new Dictionary<int,
int>();
Node temp = head;
// variable to store the maximum number
// in linked list
int maxNum = 0;
// traverse the linked list to store
// the frequency of every number and
// find the maximum integer
while (temp != null)
{
if(mymap.ContainsKey(temp.data))
mymap[temp.data] = mymap[temp.data] + 1;
else
mymap.Add(temp.data, 1);
if (maxNum < temp.data)
maxNum = temp.data;
temp = temp.next;
}
// Traverse again the linked list
while (head != null)
{
// Mark the node with frequency more
// than 1 so that we can change the
// 2nd occurrence of that number
if (mymap[head.data] > 1)
mymap[head.data] = -1;
// -1 means number has occurred
// before change its value
else if (mymap[head.data] == -1)
head.data = ++maxNum;
head = head.next;
}
}
// 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 code
public static void Main(String []args)
{
// The constructed linked list is:
// 1->3->1->4->4->2->1/
Node head = new Node(1);
head.next = new Node(3);
head.next.next = new Node(1);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(4);
head.next.next.next.next.next = new Node(2);
head.next.next.next.next.next.next = new Node(1);
Console.WriteLine("Linked list before" +
" replacing duplicates");
printList(head);
replaceDuplicates(head);
Console.WriteLine("\nLinked list after" +
" replacing duplicates");
printList(head);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// Representation of node
class Node
{
constructor(d)
{
this.data = d;
this.next = null;
}
}
// Function to insert a node at the beginning
function insert(head, item)
{
var temp = new Node(0);
temp.data = item;
temp.next = head;
head = temp;
return head;
}
// Function to replace duplicates from a
// linked list
function replaceDuplicates(head)
{
// Map to store the frequency of numbers
var mymap = {};
var temp = head;
// Variable to store the maximum number
// in linked list
var maxNum = 0;
// Traverse the linked list to store
// the frequency of every number and
// find the maximum integer
while (temp != null)
{
if (mymap.hasOwnProperty(temp.data))
mymap[temp.data] = mymap[temp.data] + 1;
else mymap[temp.data] = 1;
if (maxNum < temp.data)
maxNum = temp.data;
temp = temp.next;
}
// Traverse again the linked list
while (head != null)
{
// Mark the node with frequency more
// than 1 so that we can change the
// 2nd occurrence of that number
if (mymap[head.data] > 1) mymap[head.data] = -1;
// -1 means number has occurred
// before change its value
else if (mymap[head.data] == -1)
head.data = ++maxNum;
head = head.next;
}
}
// Function to print nodes in a given
// linked list
function printList(node)
{
while (node != null)
{
document.write(node.data + " ");
node = node.next;
}
}
// Driver code
// The constructed linked list is:
// 1->3->1->4->4->2->1/
var head = new Node(1);
head.next = new Node(3);
head.next.next = new Node(1);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(4);
head.next.next.next.next.next = new Node(2);
head.next.next.next.next.next.next = new Node(1);
document.write("Linked list before " +
"replacing duplicates <br>");
printList(head);
replaceDuplicates(head);
document.write("<br>Linked list after " +
"replacing duplicates <br>");
printList(head);
// This code is contributed by rdtank
</script>
Producción
Linked list before replacing duplicates 1 3 1 4 4 2 1 Linked list after replacing duplicates 1 3 5 4 6 2 7
Este artículo es una contribución de Chhavi . 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