Dada una lista enlazada circular , la tarea es verificar si la lista dada tiene duplicados o no.
Ejemplo:
Entrada: lista = {5, 7, 5, 1, 4, 4}
Salida: 2
Explicación: La lista dada tiene 2 índices que tienen números enteros que ya se produjeron en la lista durante el recorrido.Entrada: lista = {1, 1, 1, 1, 1}
Salida: 4
Enfoque: El problema dado tiene una solución muy similar a encontrar el conteo de duplicados en una lista enlazada . La idea es usar hash . Atraviese la lista enlazada circular dada usando el algoritmo discutido aquí . Cree un hashmap para almacenar los números enteros que se produjeron en la lista y, para cada número entero, compruebe si el número entero ya se ha producido. Mantener el conteo de enteros ya ocurridos en una variable.
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;
// Class to store Node of the list
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = NULL;
}
};
// Function to find the count of the
// duplicate integers in the list
static int checkDuplicate(Node* head)
{
if (head == NULL)
return 0;
// Stores the count of duplicate
// integers
int cnt = 0;
// Stores the integers occurred
set<int> s;
s.insert(head->data);
Node *curr = head->next;
// Loop to traverse the given list
while (curr != head) {
// If integer already occurred
if (s.find(curr->data) != s.end())
cnt++;
// Add current integer into
// the hashmap
s.insert(curr->data);
curr = curr->next;
}
// Return answer
return cnt;
}
// Driver Code
int main()
{
Node *head = new Node(5);
head->next = new Node(7);
head->next->next = new Node(5);
head->next->next->next = new Node(1);
head->next->next->next->next = new Node(4);
head->next->next->next->next->next = new Node(4);
head->next->next->next->next->next->next = head;
cout << checkDuplicate(head) << endl;
return 0;
}
// This code is contributed by Dharanendra L V.
Java
// Java program for the above approach
import java.util.HashSet;
class GFG {
// Class to store Node of the list
static class Node {
int data;
Node next;
public Node(int data)
{
this.data = data;
}
};
// Stores head pointer of the list
static Node head;
// Function to find the count of the
// duplicate integers in the list
static int checkDuplicate(Node head)
{
if (head == null)
return 0;
// Stores the count of duplicate
// integers
int cnt = 0;
// Stores the integers occurred
HashSet<Integer> s = new HashSet<>();
s.add(head.data);
Node curr = head.next;
// Loop to traverse the given list
while (curr != head) {
// If integer already occurred
if (s.contains(curr.data))
cnt++;
// Add current integer into
// the hashmap
s.add(curr.data);
curr = curr.next;
}
// Return answer
return cnt;
}
// Driver Code
public static void main(String[] args)
{
head = new Node(5);
head.next = new Node(7);
head.next.next = new Node(5);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(4);
head.next.next.next.next.next = new Node(4);
head.next.next.next.next.next.next = head;
System.out.println(checkDuplicate(head));
}
}
Python3
# Python program for the above approach # Class to store Node of the list class Node: def __init__(self, data): self.data = data; self.next = None; # Stores head pointer of the list head = None; # Function to find the count of the # duplicate integers in the list def checkDuplicate(head): if (head == None): return 0; # Stores the count of duplicate # integers cnt = 0; # Stores the integers occurred s = set(); s.add(head.data); curr = head.next; # Loop to traverse the given list while (curr != head): # If integer already occurredA if ((curr.data) in s): cnt+=1; # Add current integer into # the hashmap s.add(curr.data); curr = curr.next; # Return answer return cnt; # Driver Code if __name__ == '__main__': head = Node(5); head.next = Node(7); head.next.next = Node(5); head.next.next.next = Node(1); head.next.next.next.next = Node(4); head.next.next.next.next.next = Node(4); head.next.next.next.next.next.next = head; print(checkDuplicate(head)); # This code is contributed by umadevi9616
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Class to store Node of the list
class Node {
public int data;
public Node next;
public Node(int data)
{
this.data = data;
}
};
// Stores head pointer of the list
static Node head;
// Function to find the count of the
// duplicate integers in the list
static int checkDuplicate(Node head)
{
if (head == null)
return 0;
// Stores the count of duplicate
// integers
int cnt = 0;
// Stores the integers occurred
HashSet<int> s = new HashSet<int>();
s.Add(head.data);
Node curr = head.next;
// Loop to traverse the given list
while (curr != head) {
// If integer already occurred
if (s.Contains(curr.data))
cnt++;
// Add current integer into
// the hashmap
s.Add(curr.data);
curr = curr.next;
}
// Return answer
return cnt;
}
// Driver Code
public static void Main()
{
head = new Node(5);
head.next = new Node(7);
head.next.next = new Node(5);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(4);
head.next.next.next.next.next = new Node(4);
head.next.next.next.next.next.next = head;
Console.Write(checkDuplicate(head));
}
}
// This code is contributed by ipg2016107.
Javascript
<script>
// javascript program for the above approach
// Class to store Node of the list
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Stores head pointer of the list
var head;
// Function to find the count of the
// duplicate integers in the list
function checkDuplicate(head) {
if (head == null)
return 0;
// Stores the count of duplicate
// integers
var cnt = 0;
// Stores the integers occurred
var s = new Set();
s.add(head.data);
var curr = head.next;
// Loop to traverse the given list
while (curr != head) {
// If integer already occurred
if (s.has(curr.data))
cnt++;
// Add current integer into
// the hashmap
s.add(curr.data);
curr = curr.next;
}
// Return answer
return cnt;
}
// Driver Code
head = new Node(5);
head.next = new Node(7);
head.next.next = new Node(5);
head.next.next.next = new Node(1);
head.next.next.next.next = new Node(4);
head.next.next.next.next.next = new Node(4);
head.next.next.next.next.next.next = head;
document.write(checkDuplicate(head));
// This code is contributed by gauravrajput1
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por vishalraj10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA